CalmoSoft primes: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Added a libheader.) |
(→{{header|ALGOL 68}}: Stretch) |
||
Line 12: | Line 12: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
If there are multiple sequences with the maximum length, this will only show the first. |
If there are multiple sequences with the maximum length, this will only show the first. |
||
===Basic task=== |
|||
<syntaxhighlight lang="algol68"> |
<syntaxhighlight lang="algol68"> |
||
BEGIN # find the longest sequence of primes < 100 that sums to a prime # |
BEGIN # find the longest sequence of primes < 100 that sums to a prime # |
||
Line 72: | Line 73: | ||
Longest sequence of Calmosoft primes up to 97 has sum 953 and length 21 |
Longest sequence of Calmosoft primes up to 97 has sum 953 and length 21 |
||
7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 |
7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 |
||
</pre> |
|||
===Stretch=== |
|||
Same algorithm as the basic task sample, but with LONG INT sums. This can be run under Windows with Algol 68G version 2 by specifying <code>-heap 1024M</code> on the command line. |
|||
<br>Algol 68G version 3 will probably run out of memory (it does on the Windows 11 system I'm using). |
|||
<br>Note, Algol 68G under Windows is fully interpreted, this took around 20 seconds on the Windows 11 system. Transpiled to VB.NET with an experimental/WIP/toy transpiler, it runs in around 2 seconds. |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # find the longest sequence of primes < 100 that sums to a prime # |
|||
# called Calmosoft primes # |
|||
# returns TRUE if n is prime, FALSE otherwise - uses trial division # |
|||
PROC is prime = ( LONG INT n )BOOL: |
|||
IF n < 3 THEN n = 2 |
|||
ELIF n MOD 3 = 0 THEN n = 3 |
|||
ELIF NOT ODD n THEN FALSE |
|||
ELSE |
|||
BOOL is a prime := TRUE; |
|||
FOR f FROM 5 BY 2 WHILE f * f <= n AND ( is a prime := n MOD f /= 0 ) |
|||
DO SKIP OD; |
|||
is a prime |
|||
FI # is prime # ; |
|||
INT max prime = 50 000 000; |
|||
[ 0 : max prime ]BOOL prime; |
|||
prime[ 0 ] := prime[ 1 ] := FALSE; |
|||
prime[ 2 ] := TRUE; |
|||
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD; |
|||
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD; |
|||
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO |
|||
IF prime[ i ] THEN |
|||
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD |
|||
FI |
|||
OD; |
|||
# count and sum the primes to max prime # |
|||
INT p count := 0; |
|||
LONG INT p sum := 0; |
|||
FOR i TO max prime DO IF prime[ i ] THEN p count +:= 1; p sum +:= 1 FI OD; |
|||
# construct a list of the primes up to max prime # |
|||
[ 1 : p count ]INT prime list; |
|||
INT p pos := 0; |
|||
FOR i WHILE p pos < UPB prime list DO |
|||
IF prime[ i ] THEN prime list[ p pos +:= 1 ] := i FI |
|||
OD; |
|||
LONG INT seq sum := p sum; |
|||
# find the longest sequence that sums to a prime # |
|||
INT max start := -1; |
|||
INT max end := -1; |
|||
INT max len := -1; |
|||
FOR this start FROM LWB prime list TO UPB prime list - 1 DO |
|||
INT this end := UPB prime list; |
|||
INT this len := ( this end + 1 ) - this start; |
|||
IF this len > max len THEN |
|||
LONG INT this sum := seq sum; |
|||
BOOL this prime := FALSE; |
|||
WHILE this end >= this start |
|||
AND NOT ( this prime := is prime( this sum ) ) |
|||
AND this len > max len |
|||
DO |
|||
this sum -:= prime list[ this end ]; |
|||
this end -:= 1; |
|||
this len -:= 1 |
|||
OD; |
|||
IF this prime AND this len > max len THEN |
|||
max len := this len; # found a longer sequence # |
|||
max start := this start; |
|||
max end := this end |
|||
FI |
|||
FI; |
|||
# the start prime won't be in the next sequence # |
|||
seq sum -:= prime list[ this start ] |
|||
OD; |
|||
LONG INT max sum := 0; FOR i FROM max start TO maxend DO max sum +:= prime list[ i ] OD; |
|||
print( ( "Longest sequence of Calmosoft primes up to ", whole( prime list[ UPB prime list ], 0 ) |
|||
, " has sum ", whole( max sum, 0 ), " and length ", whole( max len, 0 ) |
|||
, newline |
|||
) |
|||
); |
|||
IF max len < 12 THEN |
|||
FOR i FROM max start TO max end DO print( ( " ", whole( prime list[ i ], 0 ) ) ) OD |
|||
ELSE |
|||
FOR i FROM max start TO max start + 6 DO print( ( " ", whole( prime list[ i ], 0 ) ) ) OD; |
|||
print( ( " ... " ) ); |
|||
FOR i FROM max end - 6 TO max end DO print( ( " ", whole( prime list[ i ], 0 ) ) ) OD |
|||
FI |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Longest sequence of Calmosoft primes up to 49999991 has sum 72619548630200 and length 3001126 |
|||
23 29 31 37 41 43 47 ... 49999853 49999877 49999883 49999897 49999903 49999921 49999991 |
|||
</pre> |
</pre> |
||