Erdős-primes: Difference between revisions
Content added Content deleted
m (→{{header|PL/M}}: better output formatting) |
No edit summary |
||
Line 599: | Line 599: | ||
The 7,875th Erdős prime is 999,721. |
The 7,875th Erdős prime is 999,721. |
||
</pre> |
</pre> |
||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
Executes in 225 ms. It could be faster with a Factorial lookup table. |
|||
<syntaxhighlight lang="Delphi"> |
|||
function IsPrime(N: integer): boolean; |
|||
{Optimised prime test - about 40% faster than the naive approach} |
|||
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 Factorial(N: Word): int64; |
|||
var I: integer; |
|||
begin |
|||
Result:= 1; |
|||
for I := 2 to N do Result:=Result * I; |
|||
end; |
|||
function IsErdosPrime(P: integer): boolean; |
|||
{Test if specified Primes is Erdos} |
|||
{i.e. all p-k! for 1<=k!<p are composite.} |
|||
var K: integer; |
|||
var F: int64; |
|||
begin |
|||
K:=1; |
|||
Result:=False; |
|||
while True do |
|||
begin |
|||
F:=Factorial(K); |
|||
if F>=P then break; |
|||
if IsPrime(P-F) then exit; |
|||
Inc(K); |
|||
end; |
|||
Result:=True; |
|||
end; |
|||
procedure FindErdosPrimes(Memo: TMemo); |
|||
{Collect and display Erdos primes} |
|||
var P,I,Cnt: integer; |
|||
var Erdos: array of integer; |
|||
var S: string; |
|||
begin |
|||
{Collect all Erdos Primes<1,000,000} |
|||
for P:=2 to 1000000 do |
|||
if IsPrime(P) then |
|||
if IsErdosPrime(P) then |
|||
begin |
|||
SetLength(Erdos,Length(Erdos)+1); |
|||
Erdos[High(Erdos)]:=P; |
|||
end; |
|||
{Display the data in several different ways} |
|||
Memo.Lines.Add('25 Erdos primes less than 2500'); |
|||
S:=''; |
|||
for I:=0 to 24 do |
|||
begin |
|||
S:=S+Format('%8d',[Erdos[I]]); |
|||
if (((I+1) mod 5)=0) or (I=24) then |
|||
begin |
|||
Memo.Lines.Add(S); |
|||
S:=''; |
|||
end; |
|||
end; |
|||
Memo.Lines.Add('Summary:'); |
|||
Memo.Lines.Add('Number of Erdos Primes < 1-million: '+IntToStr(Length(Erdos))); |
|||
Memo.Lines.Add('Last Erdos Prime < 1-million: '+IntToStr(Erdos[High(Erdos)])); |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
25 Erdos primes less than 2500 |
|||
2 101 211 367 409 |
|||
419 461 557 673 709 |
|||
769 937 967 1009 1201 |
|||
1259 1709 1831 1889 2141 |
|||
2221 2309 2351 2411 2437 |
|||
Summary: |
|||
Number of Erdos Primes < 1-million: 7875 |
|||
Last Erdos Prime < 1-million: 999721 |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |