Erdős-primes: Difference between revisions
Added Algol 68
(Added solution for Action!) |
(Added Algol 68) |
||
Line 60:
There are 25 Erdos primes
</pre>
=={{header|ALGOL 68}}==
<lang algol68>BEGIN # find Erdős primes - primes p such that p-k! is composite for all 1<=k!<p #
# returns TRUE if p is an Erdős prime #
PROC is erdos prime = ( INT p )BOOL:
IF NOT prime[ p ]
THEN FALSE
ELSE
BOOL result := TRUE;
FOR k WHILE factorial[ k ] < p AND result DO
result := NOT prime[ p - factorial[ k ] ]
OD;
result
FI # is erdos prime # ;
INT max prime = 2500; # maximum number we will consider #
# construct a table of factorials large enough for max prime #
[ 1 : 12 ]INT factorial;
factorial[ 1 ] := 1;
FOR f FROM 2 TO UPB factorial DO
factorial[ f ] := factorial[ f - 1 ] * f
OD;
# sieve the primes to max prime #
PR read "primes.incl.a68" PR
[]BOOL prime = PRIMESIEVE max prime;
# find the Erdős primes #
INT e count := 0;
IF is erdos prime( 2 ) THEN
print( ( " 2" ) );
e count +:= 1
FI;
FOR p FROM 3 BY 2 TO UPB prime DO
IF is erdos prime( p ) THEN
print( ( " ", whole( p, 0 ) ) );
e count +:= 1
FI
OD;
print( ( newline, "Found ", whole( e count, 0 ), " Erdos primes" ) )
END</lang>
{{out}}
<pre>
2 101 211 367 409 419 461 557 673 709 769 937 967 1009 1201 1259 1709 1831 1889 2141 2221 2309 2351 2411 2437
Found 25 Erdos primes
</pre>
| |||