Erdős-primes: Difference between revisions
Add APL
m (→{{header|PL/M}}: better output formatting) |
Not a robot (talk | contribs) (Add APL) |
||
| (14 intermediate revisions by 7 users not shown) | |||
Line 73:
The 7875th Erdos prime is 999721.
</pre>
=={{header|ABC}}==
<syntaxhighlight lang="abc">HOW TO REPORT prime n:
SELECT:
n < 2: FAIL
n mod 2 = 0: REPORT n=2
ELSE: REPORT NO d IN {2..floor (root n)} HAS n mod d = 0
HOW TO REPORT erdos p:
IF NOT prime p: FAIL
PUT 1, 1 IN k, k.fac
WHILE k.fac < p:
IF prime (p - k.fac): FAIL
PUT k+1 IN k
PUT k.fac*k IN k.fac
SUCCEED
PUT 0 IN nprimes
FOR n IN {1..2499}:
IF erdos n:
WRITE n>>6
PUT nprimes+1 IN nprimes
IF nprimes mod 10 = 0: WRITE/
WRITE /
WRITE "There are `nprimes` Erdos primes < 2500."/
PUT 2499 IN n
WHILE nprimes < 7875:
PUT n+2 IN n
IF erdos n: PUT nprimes + 1 IN nprimes
WRITE "The `nprimes`th Erdos prime is `n`."/</syntaxhighlight>
{{out}}
<pre> 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
There are 25 Erdos primes < 2500.
The 7875th Erdos prime is 999721.</pre>
=={{header|Action!}}==
Line 177 ⟶ 216:
999721 is Erdos prime 7875
</pre>
=={{header|APL}}==
<syntaxhighlight lang="apl">erdos_primes←{
prime ← {(⍵≥2) ∧ 0∧.≠(1↓⍳⌊⍵*÷2)|⍵}
erdos ← {(prime ⍵) ∧ ∧/~prime¨ ⍵-!⍳⌊(!⍣¯1)⍵}
e2500 ← (erdos¨e)/e←⍳2500
⎕←e2500
⎕←'There are ',(⍕⍴e2500),' Erdős numbers ≤ 2500'
}</syntaxhighlight>
{{out}}
<pre>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
There are 25 Erdős numbers ≤ 2500</pre>
=={{header|Arturo}}==
Line 598 ⟶ 649:
The 7,875th Erdős prime is 999,721.
</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|EasyLang}}==
{{trans|Action!}}
<syntaxhighlight>
fastfunc isprim num .
if num < 2
return 0
.
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
func iserdosprim p .
if isprim p = 0
return 0
.
k = 1
f = 1
while f < p
if isprim (p - f) = 1
return 0
.
k += 1
f *= k
.
return 1
.
for p = 2 to 2499
if iserdosprim p = 1
write p & " "
.
.
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
Line 615 ⟶ 811:
7875th Erdos prime is 999721
</pre>
=={{header|Factor}}==
{{works with|Factor|0.99 2021-02-05}}
Line 951 ⟶ 1,148:
The 7875th Erdős prime is 999,721
</pre>
=={{header|Lua}}==
<syntaxhighlight lang="lua">function isPrime (x)
if x < 2 then return false end
if x < 4 then return true end
if x % 2 == 0 then return false end
for d = 3, math.sqrt(x), 2 do
if x % d == 0 then return false end
end
return true
end
function primes ()
local x, maxInt = 3, 2^53
local function yieldPrimes ()
coroutine.yield(2)
repeat
if isPrime(x) then coroutine.yield(x) end
x = x + 2
until x == maxInt
end
return coroutine.wrap(function() yieldPrimes() end)
end
function factorial (n)
local f = 1
for i = 2, n do
f = f * i
end
return f
end
function isErdos (p)
local k, factK = 1
repeat
factK = factorial(k)
if isPrime(p - factK) then return false end
k = k + 1
until factK >= p
return true
end
local nextPrime, count, prime = primes(), 0
while count < 7875 do
prime = nextPrime()
if isErdos(prime) then
if prime < 2500 then io.write(prime .. " ") end
count = count + 1
end
end
print("\n\nThe 7875th Erdos prime is " .. prime)</syntaxhighlight>
{{out}}
<pre>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
The 7875th Erdos prime is 999721</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Line 974 ⟶ 1,226:
25
{7875, 999721}</pre>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay (map show erdos2500)),
Stdout ("There are " ++ show (#erdos2500) ++ " Erdos numbers <2500\n")]
where erdos2500 = filter erdos [1..2499]
erdos :: num->bool
erdos p = prime p & ~or [prime (p-k) | k <- takewhile (<p) (scan (*) 1 [2..])]
prime :: num->bool
prime n = n=2 \/ n=3, if n<=4
prime n = False, if n mod 2=0
prime n = and [n mod d ~= 0 | d <- [2..entier (sqrt n)]]</syntaxhighlight>
{{out}}
<pre>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
There are 25 Erdos numbers <2500</pre>
=={{header|Nim}}==
Line 1,385 ⟶ 1,678:
999,721 is the 7,875th Erdos prime.
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
load "stdlibcore.ring"
see "working..." + nl
row = 0
limit = 2500
for p = 1 to limit
flag = 1
if isprime(p)
for k = 1 to p
if factorial(k) < p
temp = p - factorial(k)
if not isprime(temp)
flag = 1
else
flag = 0
exit
ok
else
exit
ok
next
else
flag = 0
ok
if flag = 1
row++
see "" + p + " "
if row % 5 = 0
see nl
ok
ok
next
see nl + "Found " + row + " Erdos primes less than 2500" + nl
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
working...
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
Found 25 Erdos primes less than 2500
done...
</pre>
=={{header|RPL}}==
{{works with|HP|49}}
« 0 → p k
« 1 SF
'''WHILE''' p 'k' INCR FACT - DUP 0 > 1 FS? AND '''REPEAT'''
'''IF''' ISPRIME? '''THEN''' 1 CF '''END'''
'''END'''
DROP 1 FS?
» » '<span style="color:blue">ERDOS?</span>' STO <span style="color:grey">@ ( n → erdös(n) )</span>
« { } 2
'''WHILE''' DUP 2500 < '''REPEAT'''
'''IF''' DUP <span style="color:blue">ERDOS?</span> '''THEN''' SWAP OVER + SWAP '''END'''
NEXTPRIME
'''END'''
DROP DUP SIZE "count" →TAG
» '<span style="color:blue">TASK</span>' STO <span style="color:grey">@ ( → results )</span>
{{out}}
<pre>
2: { 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 }
1: count: 25.
</pre>
Line 1,441 ⟶ 1,809:
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program erdos_primes;
loop for e in [1..2499] | erdos e do
nprint(lpad(str e, 6));
if (n +:= 1) mod 10=0 then print; end if;
end loop;
print;
print("There are " + str n + " Erdos numbers < 2500");
e := 2499;
loop while n < 7875 do
loop until erdos e do
e +:= 2;
end loop;
n +:= 1;
end loop;
print("The " + str n + "th Erdos number is " + str e);
op erdos(p);
return prime p and not exists k in faclist p | prime (p-k);
end erdos;
op faclist(n);
f := 1;
return [[i+:=1, f*:=i](2) : until n<f](..i-1);
end op;
op prime(n);
if n<=4 then
return n in [2,3];
end if;
return odd n and not exists d in [3, 5..floor (sqrt n)] | n mod d=0;
end op;
end program;</syntaxhighlight>
{{out}}
<pre> 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
There are 25 Erdos numbers < 2500
The 7875th Erdos number is 999721</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func is_erdos_prime(p) {
Line 1,468 ⟶ 1,878:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var limit = 1e6
| |||