Unprimeable numbers: Difference between revisions
Content added Content deleted
(Added Algol 68) |
|||
Line 122: | Line 122: | ||
8 ending: 208 |
8 ending: 208 |
||
9 ending: 212159 |
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> |
</pre> |
||