Pierpont primes: Difference between revisions
Added Alghol 68
(Added Alghol 68) |
|||
Line 28:
<br>
=={{header|ALGOL 68}}==
As in the second Go sample, generates the 3-smooth number sequence to find Pierpoint Prime candidates. Uses a sliding window on the sequence to avoid having to keep it all in memory.
<lang algol68>BEGIN # find some pierpoint primes of the first kind (2^u3^v + 1) #
# and second kind (2^u3^v - 1) #
# construct a sieve of primes up to 10 000 #
[ 1 : 10 000 ]BOOL prime;
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;
# returns the minimum of a and b #
PROC min = ( INT a, b )INT: IF a < b THEN a ELSE b FI;
# returns TRUE if p is prime, FALSE otherwise #
PROC is prime = ( INT p )BOOL:
IF NOT ODD p
THEN p = 2
ELIF p <= UPB prime
THEN prime[ p ] # small enough to use the sieve #
ELSE # use trial division by the sieved primes #
BOOL probably prime := TRUE;
FOR d FROM 3 BY 2 WHILE d * d <= p AND probably prime DO
IF prime[ d ] THEN probably prime := p MOD d /= 0 FI
OD;
probably prime
FI; # is prime #
# sets the elements of pp1 to the first UPB pp1 Pierpoint primes of the #
# first kind and pp2 to the first UPB pp2 Pierpoint primes of the #
# second kind #
PROC find pierpoint = ( REF[]INT pp1, pp2 )VOID:
BEGIN
# saved 3-smooth values #
# - only the currently active part of the seuence is kept #
INT three smooth limit = 33;
[ 1 : three smooth limit * 3 ]INT s3s; FOR i TO UPB s3s DO s3s[ i ] := 0 OD;
INT pp1 pos := LWB pp1 - 1, pp2 pos := LWB pp2 - 1;
INT pp1 max = UPB pp1;
INT pp2 max = UPB pp2;
INT p2, p3, last2, last3;
INT s pos := s3s[ 1 ] := last2 := last3 := p2 := p3 := 1;
FOR n FROM 2 WHILE pp1 pos < pp1 max OR pp2 pos < pp2 max DO
# the next 3-smooth number is the lowest of the next #
# multiples of 2 and 3 #
INT m = min( p2, p3 );
IF pp1 pos < pp1 max THEN
IF INT first = m + 1;
is prime( first )
THEN # have a Pierpoint prime of the first kind #
pp1[ pp1 pos +:= 1 ] := first
FI
FI;
IF pp2 pos < pp2 max THEN
IF INT second = m - 1;
is prime( second )
THEN # have a Pierpoint prime of the second kind #
pp2[ pp2 pos +:= 1 ] := second
FI
FI;
s3s[ s pos +:= 1 ] := m;
IF m = p2 THEN p2 := 2 * s3s[ last2 +:= 1 ] FI;
IF m = p3 THEN p3 := 3 * s3s[ last3 +:= 1 ] FI;
INT last min = IF last2 > last3 THEN last3 ELSE last2 FI;
IF last min > three smooth limit THEN
# shuffle the sequence down, over the now unused bits #
INT last max = IF last2 > last3 THEN last2 ELSE last3 FI;
INT new pos := 0;
FOR pos FROM last min TO s pos DO
s3s[ new pos +:= 1 ] := s3s[ pos ]
OD;
INT diff := last min - 1;
last2 -:= diff;
last3 -:= diff;
s pos -:= diff
FI
OD
END; # find pierpoint #
# prints a table of Pierpoint primes of the specified kind #
PROC print pierpoint = ( []INT primes, STRING kind )VOID:
BEGIN
print( ( "The first "
, whole( ( UPB primes + 1 ) - LWB primes, 0 )
, " Pierpoint primes of the "
, kind
, " kind:"
, newline
)
);
INT p count := 0;
FOR i FROM LWB primes TO UPB primes DO
print( ( " ", whole( primes[ i ], -8 ) ) );
IF ( p count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
OD;
print( ( newline ) )
END; # print pierpoint #
# find the first 50 Pierpoint primes of the first and second kinds #
INT max pierpoint = 50;
[ 1 : max pierpoint ]INT pfirst;
[ 1 : max pierpoint ]INT psecond;
find pierpoint( pfirst, psecond );
# show the Pierpoint primes #
print pierpoint( pfirst, "First" );
print pierpoint( psecond, "Second" )
END</lang>
{{out}}
<pre>
The first 50 Pierpoint primes of the First kind:
2 3 5 7 13 17 19 37 73 97
109 163 193 257 433 487 577 769 1153 1297
1459 2593 2917 3457 3889 10369 12289 17497 18433 39367
52489 65537 139969 147457 209953 331777 472393 629857 746497 786433
839809 995329 1179649 1492993 1769473 1990657 2654209 5038849 5308417 8503057
The first 50 Pierpoint primes of the Second kind:
2 3 5 7 11 17 23 31 47 53
71 107 127 191 383 431 647 863 971 1151
2591 4373 6143 6911 8191 8747 13121 15551 23327 27647
62207 73727 131071 139967 165887 294911 314927 442367 472391 497663
524287 786431 995327 1062881 2519423 10616831 17915903 18874367 25509167 30233087
</pre>
=={{header|C}}==
| |||