De Polignac numbers: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
No edit summary |
||
Line 371: | Line 371: | ||
Ten thousandth: 273,421 |
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> |
</pre> |
||