CalmoSoft primes: Difference between revisions
→{{header|ALGOL 68}}: Stretch
m (→{{header|Wren}}: Added a libheader.) |
(→{{header|ALGOL 68}}: Stretch) |
||
Line 12:
=={{header|ALGOL 68}}==
If there are multiple sequences with the maximum length, this will only show the first.
===Basic task===
<syntaxhighlight lang="algol68">
BEGIN # find the longest sequence of primes < 100 that sums to a prime #
Line 72 ⟶ 73:
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
</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>
| |||