CalmoSoft primes: Difference between revisions
Algol 68 Stretch - combine sieving the primes and converting the sieve into a list
(Added Java solution) |
(Algol 68 Stretch - combine sieving the primes and converting the sieve into a list) |
||
Line 81:
Uses Algol 68G's LONG LONG INT for the Millar Rabin test.
To run this with Algol 68G, you need <code>-heap 512M</code> on the command line.
<br>Note the
{{libheader|ALGOL 68-primes}}
<syntaxhighlight lang="algol68">
Line 88:
PR read "primes.incl.a68" PR
INT max prime = 50 000 000;
# sieve, count and sum the primes to max prime and replace the
prime[ 1 ] := 2; # the first prime in the list #
INT p count := 1; ▼
prime[ 2 ] := yes; # first TRUE sieve value #
LONG INT p sum := 2;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] :=
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] :=
INT root max prime = ENTIER sqrt( UPB prime );
FOR i FROM 3 BY 2 TO root max prime DO
IF prime[ i ] = yes THEN
prime[ p count +:= 1 ] := i;
p sum +:= i;
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] :=
FI
OD;
FOR i FROM root max prime + IF ODD root max prime THEN 2 ELSE 1 FI BY 2 TO max prime DO
IF prime[ i ] = yes THEN
prime[ p count +:= 1 ] := i;
p sum +:= i
FI
▲ # construct a list of the primes up to max prime #
OD;
LONG INT seq sum := p sum;
Line 122 ⟶ 118:
INT max len := -1;
LONG INT max sum := -1;
FOR this start
WHILE
INT this end :=
INT this len := ( this end + 1 ) - this start;
LONG INT this sum := seq sum;
Line 130 ⟶ 126:
IF this start = 1 THEN
# the first prime is 2, the sequence must have even length #
this sum -:= prime
this end -:= 1;
this len -:= 1
Line 137 ⟶ 133:
IF this start > 1 THEN
# the first prime isn't 2, the sequence must have odd length #
this sum -:= prime
this end -:= 1;
this len -:= 1
Line 149 ⟶ 145:
FI
DO
this sum -:= prime
this sum -:= prime
this end -:= 1;
this len -:= 2
Line 164 ⟶ 160:
DO
# the start prime won't be in the next sequence #
seq sum -:= prime
OD;
print( ( "Longest sequence of Calmosoft primes up to ", whole( prime
, " has sum ", whole( max sum, 0 ), " and length ", whole( max len, 0 )
, newline
Line 172 ⟶ 168:
);
IF max len < 12 THEN
FOR i FROM max start TO max end DO print( ( " ", whole( prime
ELSE
FOR i FROM max start TO max start + 6 DO print( ( " ", whole( prime
print( ( " ... " ) );
FOR i FROM max end - 6 TO max end DO print( ( " ", whole( prime
FI
END
|