Pandigital prime: Difference between revisions

Line 17:

=={{header|ALGOL 68}}==

===Common code===

Uses the observations in the Factor sample - the prime we are looking for can only have 7 or 4 digits.

<lang algol68> # ~~permutation~~ ~~code~~ ~~from~~ ~~the~~ ~~Algol~~ 68 ~~Permutations~~ by ~~swapping task~~ #

<lang algol68>BEGIN # Find the largest n-digit prime that contains all the digits 1..n #

⚫

# As noted in the Factor sample, only 7 and 4 digit primes need be #

⚫

# considered: 1 is not prime, all 2, 3, 5, 6, 8 and 9 digit #

⚫

# pandigital numbers are divisible by 3 #

⚫

# Also find the largest n+1 digit prime that contains all the #

# digits 0..n (only 5 and 8 digit numbers need be considered as #

# the 0 digit does not affect divisibility by 3) #

# permutation code from the Algol 68 Permutations by swapping task #

# entry - uses Heap's algorithm - based on the pseudo code on the #

# Wikipedia page for Heap's Algorithm #

Line 83:

Line 89:

# array of digits to permute for the numbers #

[ f : n ]INT digits; FOR i FROM LWB digits TO UPB digits DO digits[ i ] := i OD;

# array to hold the permuted digits, there will be ( ( n + 1 ) - f )! elements #

# array to hold the permuted digits, there will be ( ( n + 1 ) - f)! elements #

INT factorial n := 1; FOR i FROM 2 TO ( n + 1 ) - f DO factorial n *:= i OD;

[ 0 : factorial n - 1 ]INT permuted digits;

Line 105:

Line 111:

pd prime

END # try pd prime # ;

# trys to find the maximem pandigital/pandigital0 prime #

⚫

</lang>

PROC find pd prime = ( INT first digit, STRING title )VOID:

⚫

IF # first try digits up to 7 then up to 4 if we can't find one with pt to 7 #

===Digits 1 to n===

⚫

INT pd prime := try pd prime( first digit, 7 );

<lang algol68>BEGIN # Find the largest n-digit prime that contains all the digits 1..n #

# As ~~noted~~ in ~~the~~ ~~Factor~~ ~~sample,~~ ~~only~~ 7 ~~and~~ 4 ~~digit primes need be #~~

pd prime > 0

⚫

THEN

⚫

# considered: 1 is not prime, all 2, 3, 5, 6, 8 and 9 digit #

# ~~pandigital~~ ~~numbers~~ ~~are~~ ~~divisible~~ by 3 #

print( ( "max ", title, " prime: ", whole( pd prime, 0 ), newline ) )

⚫

ELIF pd prime := try pd prime( first digit, 4 );

# insert the common code here #

⚫

pd prime > 0

# first try a 7 digit number then a 4 digit number if we can't find a 7 digit one #

⚫

THEN

⚫

IF INT pd prime := try pd prime( 1, 7 );

pd prime > 0

print( ( "max ", title, " prime: ", whole( pd prime, 0 ), newline ) )

~~THEN~~

ELSE

print( ( "~~max~~ ~~pandigital~~ ~~prime:~~ ", ~~whole( pd prime~~, 0 ), newline ) )

print( ( "Can't find a ", title, " prime", newline ) )

~~ELIF~~ pd ~~prime~~ := ~~try~~ pd prime~~( 1,~~ 4 );

FI # find pd prime # ;

~~pd prime > 0~~

# task #

find pd prime( 1, "pandigital" );

⚫

THEN

~~print( ( "max pandigital~~ prime~~: ", whole~~( ~~pd prime,~~ 0 ), ~~newline )~~ )

find pd prime( 0, "pandigital0" )

⚫

END</lang>

ELSE

print( ( "Can't find a pandigital prime", newline ) )

FI

END

</lang>

<pre>

max pandigital prime: 7652413

⚫

max pandigital0 prime: 76540231

</pre>

===Digits 0 to n===

Also uses the observations in the Factor sample - the prime we are looking for can only have 8 or 5 digits.

⚫

~~<lang~~ ~~algol68>BEGIN~~ # ~~Find~~ the largest n+1 digit prime that contains all the ~~digits~~ ~~0..n~~ #

⚫

# As noted in the Factor sample, only 8 and 5 digit primes need be #

# considered: 10 is not prime, all 3, 4, 6, 7 and 9 digit #

⚫

# pandigital numbers are divisible by 3 #

# insert the common code here #

⚫

# first try an 8 ~~digit~~ ~~number~~ then a 5 ~~digit number~~ if we can't find an 8 ~~digit~~ ~~one~~ #

IF INT pd prime := try pd prime( 0, 7 );

⚫

pd prime > 0

⚫

THEN

print( ( "max pandigital prime: ", whole( pd prime, 0 ), newline ) )

⚫

ELIF pd prime := try pd prime( 0, 4 );

pd prime > 0

THEN

print( ( "max pandigital prime: ", whole( pd prime, 0 ), newline ) )

ELSE

print( ( "Can't find a pandigital prime", newline ) )

FI

END</lang>

<pre>

⚫

max ~~pandigital~~ prime: 76540231

</pre>