CalmoSoft primes: Difference between revisions
Algol 68 Stretch sample - fix performance issues and optimise a little
(Added C++ solution) |
(Algol 68 Stretch sample - fix performance issues and optimise a little) |
||
Line 76:
===Stretch===
Basically the same algorithm as the Algol 68 Basic task sample but stops searching when there can't be a longer sequence.
<br>Also, if the first prime in the sequence is 2, the sequence must have even length, otherwise it must have odd length.
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT for the Millar Rabin test.
To run this with Algol 68G
<br>Took about
<br>Note Algol 68G is fully interpreted on Windows.
{{libheader|ALGOL 68-primes}}
Line 87 ⟶ 88:
# called Calmosoft primes #
PR read "primes.incl.a68" PR
INT max prime
# sieve, count and sum the primes to max prime #
[ 0 : max prime ]BOOL prime;
prime[ 0 ] := prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
INT p count := 1;
LONG INT p sum := 2;
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 root max prime DO
IF prime[ i ] THEN
p count +:= 1;
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
FI
OD;
FI
OD;
# construct a list of the primes up to max prime #
[ 1 : p count ]INT prime list;
Line 113 ⟶ 122:
INT max end := -1;
INT max len := -1;
FOR this start FROM LWB prime list TO UPB prime list - 1
WHILE
INT this end := UPB prime list;
INT this len := ( this end + 1 ) - this start;
LONG INT this sum := seq sum;
IF ODD this len THEN
IF this start = 1 THEN
# the first prime is 2, the sequence must have even length #
this sum -:= prime list[ this end ];
this end -:= 1;
this len -:= 1
FI
ELSE
IF this start > 1 THEN
# the first prime isn't 2, the sequence must have odd length #
this sum -:= prime list[ this end ];
this end -:= 1;
this len -:= 1
FI
FI;
IF this len > max len THEN
▲ BOOL this prime := FALSE;
WHILE IF this end < this start OR this len < max len
THEN FALSE
Line 124 ⟶ 150:
FI
DO
this sum -:= prime list[ this end ];
this sum -:= prime list[ this end -:= 1 ];
this end -:= 1;
this len -:=
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;
max sum := this sum
FI
FI;
( p count - this start ) > max len
DO
# the start prime won't be in the next sequence #
seq sum -:= prime list[ this start ]
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 )
Line 144 ⟶ 173:
);
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;
| |||