Unprimeable numbers: Difference between revisions
Added Algol 68
(Added Algol 68) |
|||
Line 122:
8 ending: 208
9 ending: 212159
</pre>
=={{header|ALGOL 68}}==
If running this with Algol 68G under Windows (and possibly other platforms) you will need to increase the heap size by specifying e.g. <code>-heap 256M</code> on the command line.
{{libheader|ALGOL 68-primes}}
<lang algol68>BEGIN # find unprimable numbers - numbers which can't be made into a prime by changing one digit #
# construct a sieve of primes up to max prime #
PR read "primes.incl.a68" PR
INT max prime = 9 999 999;
[]BOOL prime = PRIMESIEVE max prime;
# returns TRUE if n is unprimeable, FALSE otherwise #
PROC is unprimeable = ( INT n )BOOL:
IF n < 100
THEN FALSE
ELIF prime[ n ]
THEN FALSE
ELSE
# need to try changing a digit #
INT last digit = n MOD 10;
INT leading digits = n - last digit;
IF prime[ leading digits + 1 ] THEN FALSE
ELIF prime[ leading digits + 3 ] THEN FALSE
ELIF prime[ leading digits + 7 ] THEN FALSE
ELIF prime[ leading digits + 9 ] THEN FALSE
ELIF NOT ODD last digit OR last digit = 5
THEN
# the final digit is even or 5, changing the other digits can't make a prime #
# unless we change the first digit to 0 #
INT p10 := 10;
INT l10 := 1;
WHILE p10 <= n DO
l10 := p10;
p10 *:= 10
OD;
NOT prime[ n MOD l10 ]
ELSE
# must try changing the other digoits #
INT m10 := 10;
INT r10 := 100;
BOOL result := TRUE;
WHILE result AND n > r10 DO
INT base = ( ( n OVER r10 ) * r10 ) + ( n MOD m10 );
FOR i FROM 0 TO 9 WHILE result DO
result := NOT prime[ base + ( i * m10 ) ]
OD;
m10 *:= 10;
r10 *:= 10
OD;
IF result THEN
# still not unprimeable, try changing the first digit #
INT base = n MOD m10;
FOR i FROM 0 TO 9 WHILE result DO
result := NOT prime[ base + ( i * m10 ) ]
OD
FI;
result
FI
FI # is unprimeable # ;
# returns a string representation of n with commas #
PROC commatise = ( LONG LONG INT n )STRING:
BEGIN
STRING result := "";
STRING unformatted = whole( n, 0 );
INT ch count := 0;
FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO
IF ch count <= 2 THEN ch count +:= 1
ELSE ch count := 1; "," +=: result
FI;
unformatted[ c ] +=: result
OD;
result
END; # commatise #
# find unprimeable numbers #
INT u count := 0;
INT d count := 0;
[ 0 : 9 ]INT first unprimeable := []INT( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 )[ AT 0 ];
FOR i FROM 100 WHILE i < UPB prime AND d count < 10 DO
IF is unprimeable( i ) THEN
u count +:= 1;
IF u count = 1 THEN
print( ( "First 25 unprimeable numbers: ", whole( i, 0 ) ) )
ELIF u count < 25 THEN
print( ( " ", whole( i, 0 ) ) )
ELIF u count = 600 THEN
print( ( newline, "600th unprimeable number: ", commatise( i ) ) )
FI;
INT final digit = i MOD 10;
IF first unprimeable[ final digit ] = 0 THEN
# first unprimeable number with this final digit #
d count +:= 1;
first unprimeable[ final digit ] := i
FI
FI
OD;
# show the first unprimeable number that ends with each digit #
print( ( newline ) );
FOR i FROM 0 TO 9 DO
print( ( "First unprimeable number ending in "
, whole( i, 0 )
, ": "
, commatise( first unprimeable[ i ] )
, newline
)
)
OD
END</lang>
{{out}}
<pre>
First 25 unprimeable numbers: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622
600th unprimeable number: 5,242
First unprimeable number ending in 0: 200
First unprimeable number ending in 1: 595,631
First unprimeable number ending in 2: 322
First unprimeable number ending in 3: 1,203,623
First unprimeable number ending in 4: 204
First unprimeable number ending in 5: 325
First unprimeable number ending in 6: 206
First unprimeable number ending in 7: 872,897
First unprimeable number ending in 8: 208
First unprimeable number ending in 9: 212,159
</pre>
| |||