CalmoSoft primes: Difference between revisions
Algol 68 - added a (correct this time, I think) stretch sample
(→{{header|Go}}: Updated in line with Wren entry of which it is a translation.) |
(Algol 68 - added a (correct this time, I think) stretch sample) |
||
Line 74:
7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
</pre>
===Stretch===
Basically the same algorithm as the Algol 68 Basic task sample.
<br>Runs in around two seconds when transpiled to VB.NET using an experimental/WIP/toy transpiler.
<br>To run it with Algol 68G version 2, you need <code>-heap 512M</code> on the command line.
<br>Took over a minute with Algol 68G on the Windows 11 system I'm using.
<syntaxhighlight lang="algol68">
BEGIN # find the longest sequence of primes < 50 000 000 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 LENG f * LENG 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 +:= i 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 IF this end < this start OR this len < max len
THEN FALSE
ELSE NOT ( this prime := is prime( this sum ) )
FI
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 max end 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 72618848632313 and length 3001117
7 11 13 17 19 23 29 ... 49999693 49999699 49999711 49999739 49999751 49999753 49999757
/pre>
=={{header|Arturo}}==
| |||