CalmoSoft primes: Difference between revisions
Content added Content deleted
(→{{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: | Line 74: | ||
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> |
</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}}== |
=={{header|Arturo}}== |