De Polignac numbers: Difference between revisions
no edit summary
Alextretyak (talk | contribs) (Added 11l) |
No edit summary |
||
Line 371:
Ten thousandth: 273,421
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Uses a little algebra to simplify the code. {We are looking for 2^I + Prime = N therefore this 2^I - N should be prime if N is not a De Polignac number. Run Time: 111 ms on a Rizen 7 processor.
<syntaxhighlight lang="Delphi">
function IsPrime(N: integer): boolean;
{Fast, optimised prime test}
var I,Stop: integer;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
function IsPolignac(N: integer): boolean;
{We are looking for 2^I + Prime = N
Therefore this 2^I - N should be prime}
var Pw2: integer;
begin
Result:=False;
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;
Pw2:=Pw2 shl 1;
end;
Result:=True;
end;
procedure ShowPolignacNumbers(Memo: TMemo);
{Show the first 50, 1000th and 10,000th Polignac numbers}
var I,Cnt: integer;
var S: string;
begin
Memo.Lines.Add('First 50 Polignac numbers:');
I:=1; Cnt:=0; S:='';
{Iterate through all odd numbers}
while true do
begin
if IsPolignac(I) then
begin
S:=S+Format('%10.0n',[I*1.0]);
Inc(Cnt);
if (Cnt mod 10)=0 then
begin
Memo.Lines.Add(S);
S:='';
end;
end;
Inc(I,2);
if Cnt>=50 then break;
end;
if S<>'' then Memo.Lines.Add(IntToStr(I));
while true do
begin
if IsPolignac(I) then
begin
Inc(Cnt);
if Cnt=1000 then Memo.Lines.Add('1,000th = '+Format('%10.0n',[I*1.0]));
if Cnt=10000 then
begin
Memo.Lines.Add('10,000th = '+Format('%10.0n',[I*1.0]));
break;
end;
end;
Inc(I,2);
end;
end;
</syntaxhighlight>
{{out}}
<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
1,000th = 31,941
10,000th = 273,421
</pre>
| |||