De Polignac numbers: Difference between revisions
→{{header|Nim}}: append {{header|Pascal}} trans Delphi
(Created Nim solution.) |
(→{{header|Nim}}: append {{header|Pascal}} trans Delphi) |
||
Line 878:
The 1000th de Polignac number is 31941
The 10000th de Polignac number is 273421
</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
{{trans|Delphi}}
slightly modified for console
<syntaxhighlight lang="pascal">
program DePolignacNum;
{$IFDEF FPC}{$MODE DELPHI}{$Optimization ON,ALL} {$ENDIF}
{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}
uses
sysutils;
function IsPrime(n: Uint32): boolean;
{Fast, optimised prime test}
const
DeltaMOD235: array[0..7] of Uint32 =(4,2,4,2,4,6,2,6);
var
pr,idx : NativeUint;
begin
if n < 32 then
Exit(n in [2,3,5,7,11,13,17,19,23,29,31]);
IF n AND 1 = 0 then EXIT(false);
IF n mod 3 = 0 then EXIT(false);
IF n mod 5 = 0 then EXIT(false);
pr := 7;
idx := 0;
repeat
if sqr(pr) >n then
EXIT(true);
if n mod pr = 0 then
EXIT(false);
pr += DeltaMOD235[idx];
idx := (idx+1) AND 7;
until false;
end;
function IsPolignac(N: Uint32): boolean;
{We are looking for 2^I + Prime = N
Therefore this 2^I - N should be prime}
var
Pw2: Uint32;
begin
Pw2:=1;
{Test all powers of less than N}
while Pw2<N do
begin
{If the difference is prime, it is not Polignac}
if IsPrime(N-Pw2) then
EXIT(false);
//Pw2:=Pw2 shl 1;
Pw2 +=Pw2;
end;
Result:=True;
end;
procedure ShowPolignacNumbers;
{Show the first 50, 1000th and 10,000th Polignac numbers}
var
I,Cnt,lmt: Uint32;
S: string;
begin
writeln('First 50 Polignac numbers:');
I:=1; Cnt:=0; S:='';
{Iterate through all odd numbers}
lmt := 10;
while true do
begin
if IsPolignac(I) then
begin
S:=S+Format('%6.0n',[I*1.0]);
Inc(Cnt);
if Cnt = lmt then
begin
writeln(S);
S:='';
inc(lmt,10);
end;
end;
Inc(I,2);
if Cnt>=50 then break;
end;
writeln;
lmt := 100;
repeat
if IsPolignac(I) then
begin
Inc(Cnt);
if Cnt=lmt then
begin
writeln(Format('%10.0nth %10.0n',[cnt*1.0,I*1.0]));
lmt *= 10;
if lmt > 10000 then
BREAK;
end;
end;
Inc(I,2);
until false;
end;
var
T : Int64;
BEGIN
//wait for change in GetTickCount64
T := GetTickCount64+1;repeat until T <= GetTickCount64;
ShowPolignacNumbers;
Writeln(GetTickCount64-T,' ms');
end.</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
First 50 Polignac numbers:
1 127 149 251 331 337 373 509 599 701
757 809 877 905 907 959 977 997 1,019 1,087
1,199 1,207 1,211 1,243 1,259 1,271 1,477 1,529 1,541 1,549
1,589 1,597 1,619 1,649 1,657 1,719 1,759 1,777 1,783 1,807
1,829 1,859 1,867 1,927 1,969 1,973 1,985 2,171 2,203 2,213
100th 4,153
1,000th 31,941
10,000th 273,421
162 ms // 32 ms @home Ryzen 5600G on Linux 64-bit
</pre>
| |||