De Polignac numbers: Difference between revisions
Added Algol 68 and Algol W
(Added Action!) |
(Added Algol 68 and Algol W) |
||
Line 30:
=={{header|Action!}}==
{{Trans|PL/M}}
which is based on the ALGOL 68 sample.
{{libheader|Action! Sieve of Eratosthenes}}
<syntaxhighlight lang="action!">
Line 94 ⟶ 95:
1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
1829 1859 1867 1927 1969 1973 1985 2171 2203 2213
</pre>
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # find some De Polignac Numbers - positive odd numbers that can't be #
# written as p + 2^n for some prime p and integer n #
INT max number = 500 000; # maximum number we will consider #
# sieve the primes to max number #
[ 0 : max number ]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;
# table of powers of 2 greater than 2^0 ( up to around 2 000 000 ) #
# increase the table size if max number > 2 000 000 #
[ 1 : 20 ]INT powers of 2;
BEGIN
INT p2 := 1;
FOR i TO UPB powers of 2 DO
powers of 2[ i ] := ( p2 *:= 2 )
OD
END;
# the numbers must be odd and not of the form p + 2^n #
# either p is odd and 2^n is even and hence n > 0 and p > 2 #
# or 2^n is odd and p is even and hence n = 0 and p = 2 #
INT dp count := 0;
# n = 0, p = 2 - the only possibility is 3 #
FOR i BY 2 TO 3 DO
INT p = 2;
IF p + 1 /= i THEN
print( ( whole( i, -5 ) ) );
dp count +:= 1
FI
OD;
# n > 0, p > 2 #
FOR i FROM 5 BY 2 TO max number DO
BOOL found := FALSE;
FOR p TO UPB powers of 2 WHILE NOT found AND i > powers of 2[ p ] DO
found := prime[ i - powers of 2[ p ] ]
OD;
IF NOT found THEN
IF ( dp count +:= 1 ) <= 50 THEN
print( ( whole( i, -5 ) ) );
IF dp count MOD 10 = 0 THEN print( ( newline ) ) FI
ELIF dp count = 1 000 OR dp count = 10 000 THEN
print( ( "The ", whole( dp count, -5 )
, "th De Polignac number is ", whole( i, -7 )
, newline
)
)
FI
FI
OD;
print( ( "Found ", whole( dp count, 0 )
, " De Polignac numbers up to ", whole( max number, 0 )
, newline
)
)
END
</syntaxhighlight>
{{out}}
<pre>
1 127 149 251 331 337 373 509 599 701
757 809 877 905 907 959 977 997 1019 1087
1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
1829 1859 1867 1927 1969 1973 1985 2171 2203 2213
The 1000th De Polignac number is 31941
The 10000th De Polignac number is 273421
Found 19075 De Polignac numbers up to 500000
</pre>
=={{header|ALGOL W}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="algolw">
begin % find some De Polignac numbers - positive odd numbers that can't be %
% written as p + 2^n for some prime p and integer n %
integer MAX_NUMBER; % maximum number we will consider %
integer MAX_POWER; % maximum powerOf2 < MAX_NUMBER %
MAX_NUMBER := 500000;
MAX_POWER := 20;
begin
logical array prime ( 0 :: MAX_NUMBER );
integer array powersOf2 ( 1 :: MAX_POWER );
integer dpCount;
% sieve the primes to MAX_NUMBER %
begin
integer rootMaxNumber;
rootMaxNumber:= entier( sqrt( MAX_NUMBER ) );
prime( 0 ) := prime( 1 ) := false;
prime( 2 ) := true;
for i := 3 step 2 until MAX_NUMBER do prime( i ) := true;
for i := 4 step 2 until MAX_NUMBER do prime( i ) := false;
for i := 3 step 2 until rootMaxNumber do begin
if prime( i ) then begin
integer i2;
i2 := i + i;
for s := i * i step i2 until MAX_NUMBER do prime( s ) := false
end if_prime_i_and_i_lt_rootMaxNumber
end for_i
end;
% table of powers of 2 greater than 2^0 ( up to around 2 000 000 ) %
% increase the table size if MAX_NUMBER > 2 000 000 %
begin
integer p2;
p2 := 1;
for i := 1 until MAX_POWER do begin
p2 := p2 * 2;
powersOf2( i ) := p2
end for_i
end;
% the numbers must be odd and not of the form p + 2^n %
% either p is odd and 2^n is even and hence n > 0 and p > 2 %
% or 2^n is odd and p is even and hence n = 0 and p = 2 %
% n = 0, p = 2 - the only possibility is 3 %
dpCount := 0;
for i := 1 step 2 until 3 do begin
integer p;
p := 2;
if p + 1 not = i then begin
dpCount := dpCount + 1;
writeon( i_w := 5, i )
end if_p_plus_1_ne_i
end for_i ;
% n > 0, p > 2 %
for i := 5 step 2 until MAX_NUMBER do begin
logical found;
integer p;
found := false;
p := 1;
while p <= MAX_POWER and not found and i > powersOf2( p ) do begin
found := prime( i - powersOf2( p ) );
p := p + 1
end while_not_found_and_have_a_suitable_power ;
if not found then begin
dpCount := dpCount + 1;
if dpCount <= 50 then begin
writeon( i_w := 5, i );
if dpCount rem 10 = 0 then write()
end
else if dpCount = 1000 or dpCount = 10000 then begin
write( i_w := 5, s_w := 0, "The ", dpCount
, "th De Polignac number is ", i
)
end if_various_DePolignac_numbers
end if_not_found
end for_i;
write( i_w := 1, s_w := 0
, "Found ", dpCount, " De Polignac numbers up to ", MAX_NUMBER
)
end
end.
</syntaxhighlight>
{{out}}
<pre>
1 127 149 251 331 337 373 509 599 701
757 809 877 905 907 959 977 997 1019 1087
1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
1829 1859 1867 1927 1969 1973 1985 2171 2203 2213
The 1000th De Polignac number is 31941
The 10000th De Polignac number is 273421
Found 19075 De Polignac numbers up to 500000
</pre>
| |||