Pandigital prime: Difference between revisions
→{{header|ALGOL 68}}: Tweaked code and added solution for digits 0..n
m (→{{header|Phix}}: added a remove "?n" note) |
(→{{header|ALGOL 68}}: Tweaked code and added solution for digits 0..n) |
||
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>
# 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 #▼
# entry - uses Heap's algorithm - based on the pseudo code on the #
# Wikipedia page for Heap's Algorithm #
Line 28 ⟶ 25:
PROC generate = ( INT k, REF[]INT a, REF[]INT p, REF INT p pos )VOID:
IF k = 1 THEN
INT
FI
ELSE
# Generate permutations with kth unaltered #
Line 49:
FI # generate # ;
# generate permutations of a, p is used to hold the output #
# returns the number of permutations stored #
PROC permute digits = ( REF[]INT a, REF[]INT p )
BEGIN
INT p pos :=
generate( ( UPB a + 1 ) - LWB a, a[ AT 0 ], p[ AT 0 ], p pos );
p pos
END # permute digits # ;
# Quicksorts in-place the array of integers a, from lb to ub #
Line 76 ⟶ 78:
quicksort( a, left, ub )
FI # quicksort # ;
# attenmpt to find the maximum
PROC try pd prime = ( INT f, INT n )INT:
BEGIN
# array of digits to permute for the numbers #
[
# 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;
# permute the digits #
INT p count = permute digits( digits, permuted digits );
# sort the permuted numbers, assuming the prime is near the high end #
quicksort( permuted digits, LWB permuted digits,
# try finding a prime - use trial division to test for primality #
INT pd prime := 0;
FOR p pos FROM
INT p = permuted digits[ p pos ];
# and we know
BOOL prime :=
FOR i FROM 7 BY 2 TO ENTIER sqrt(p) WHILE prime := p MOD i /= 0 DO SKIP OD;
IF prime
pd prime :=
▲ pd prime := p
▲ FI
FI
OD;
pd prime
END # try pd prime # ;
</lang>
===Digits 1 to n===
<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 #
# insert the common code here #
# first try a 7 digit number then a 4 digit number if we can't find a 7 digit one #
IF INT pd prime := try pd prime( 1, 7 );
pd prime > 0
THEN
print( ( "max pandigital prime: ", whole( pd prime, 0 ), newline ) )
ELIF pd prime := try pd prime( 1, 4 );
pd prime > 0
THEN
Line 118 ⟶ 125:
print( ( "Can't find a pandigital prime", newline ) )
FI
END
</lang>
{{out}}
<pre>
max pandigital prime: 7652413
</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-digit prime that contains all the digits 1..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>
{{out}}
<pre>
max pandigital prime: 76540231
</pre>
| |||