Rosetta Code

Erdős-primes: Difference between revisions

Page Discussion

Erdős-primes (view source)

Revision as of 14:16, 10 April 2024

44,886 bytes added ,  1 month ago
Add APL
m (→‎{{header|REXX}}: <tt ==> <tt>)
(Add APL)
 
(65 intermediate revisions by 28 users not shown)
Line 15:
:* &nbsp; the OEIS entry: &nbsp; [http://oeis.org/A064152 A064152 Erdos primes].
<br><br>
 
=={{header|11l}}==
{{trans|Nim}}
 
<syntaxhighlight lang="11l">F primes_upto(limit)
V is_prime = [0B] * 2 [+] [1B] * (limit - 1)
L(n) 0 .< Int(limit ^ 0.5 + 1.5)
I is_prime[n]
L(i) (n * n .. limit).step(n)
is_prime[i] = 0B
R is_prime
 
V is_prime = primes_upto(1'000'000)
V primeList = enumerate(is_prime).filter((i, prime) -> prime).map((i, prime) -> i)
 
[Int] factorials
L(n) 1..
I factorial(n) >= 1'000'000
L.break
factorials.append(factorial(n))
 
F isErdosPrime(p)
L(f) :factorials
I f >= p
L.break
I :is_prime[p - f]
R 0B
R 1B
 
[Int] erdosList2500
L(p) primeList
I p >= 2500
L.break
I isErdosPrime(p)
erdosList2500.append(p)
 
print(‘Found ’erdosList2500.len‘ Erdos primes less than 2500:’)
L(prime) erdosList2500
print(‘#5’.format(prime), end' I (L.index + 1) % 10 == 0 {"\n"} E ‘ ’)
print()
 
V count = 0
L(p) primeList
I isErdosPrime(p)
count++
I count == 7875
print("\nThe 7875th Erdos prime is "p‘.’)
L.break</syntaxhighlight>
 
{{out}}
<pre>
Found 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
 
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!}}==
{{libheader|Action! Sieve of Eratosthenes}}
<syntaxhighlight lang="action!">INCLUDE "H6:SIEVE.ACT"
 
BYTE Func IsErdosPrime(INT x BYTE ARRAY primes)
INT k,f
 
IF primes(x)=0 THEN
RETURN (0)
FI
 
k=1 f=1
WHILE f<x
DO
IF primes(x-f) THEN
RETURN (0)
FI
k==+1
f==*k
OD
RETURN (1)
 
PROC Main()
DEFINE MAX="2499"
BYTE ARRAY primes(MAX+1)
INT i,count=[0]
 
Put(125) PutE() ;clear the screen
Sieve(primes,MAX+1)
FOR i=2 TO MAX
DO
IF IsErdosPrime(i,primes) THEN
PrintI(i) Put(32)
count==+1
FI
OD
PrintF("%E%EThere are %I Erdos primes",count)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Erd%C5%91s-primes.png Screenshot from Atari 8-bit computer]
<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
</pre>
 
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # find Erdős primes - primes p where p-k! is composite for all 1<=k!<p #
# returns TRUE if p is an Erdős prime #
PROC is erdos prime = ( INT p )BOOL:
IF NOT prime[ p ]
THEN FALSE
ELSE
BOOL result := TRUE;
FOR k WHILE factorial[ k ] < p AND result DO
result := NOT prime[ p - factorial[ k ] ]
OD;
result
FI # is erdos prime # ;
INT max prime = 1 000 000; # maximum number we will consider #
INT max erdos = 7 875; # maximum Erdős prime to find #
# construct a table of factorials large enough for max prime #
[ 1 : 12 ]INT factorial;
factorial[ 1 ] := 1;
FOR f FROM 2 TO UPB factorial DO
factorial[ f ] := factorial[ f - 1 ] * f
OD;
PR read "primes.incl.a68" PR # include prime utilities #
[]BOOL prime = PRIMESIEVE max prime; # sieve the primes to max prime #
INT max show = 2 500;
# find the Erdős primes, showing the ones up to max show #
INT e count := 0;
IF is erdos prime( 2 ) THEN
print( ( " 2" ) );
e count +:= 1
FI;
INT last erdos := 0;
FOR p FROM 3 BY 2 TO max show DO
IF is erdos prime( p ) THEN
print( ( " ", whole( p, 0 ) ) );
last erdos := p;
e count +:= 1
FI
OD;
print( ( newline, "Found ", whole( e count, 0 )
, " Erdos primes up to ", whole( max show, 0 ), newline ) );
# find the max erdos'th Erdős prime #
FOR p FROM max show WHILE e count < max erdos DO
IF is erdos prime( p ) THEN
last erdos := p;
e count +:= 1
FI
OD;
print( ( whole( last erdos, 0 ), " is Erdos prime ", whole( e count, 0 ), newline ) )
END
</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
Found 25 Erdos primes up to 2500
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}}==
 
<syntaxhighlight lang="rebol">factorials: map 1..20 => [product 1..&]
erdos?: function [x][
if not? prime? x -> return false
 
loop factorials 'f [
if f >= x -> break
if prime? x - f -> return false
]
return true
]
 
loop split.every:10 select 2..2500 => erdos? 'a ->
print map a => [pad to :string & 5]</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>
 
=={{header|AWK}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="awk">
# syntax: GAWK -f ERDOS-PRIMES.AWK
# converted from FreeBASIC
BEGIN {
while (++i) {
if (is_erdos_prime(i)) {
if (i < 2500) {
printf("%d ",i)
count1++
}
if (++count2 == 7875) {
printf("\nErdos primes 1-2500: %d\nErdos prime %d: %d\n",count1,count2,i)
break
}
}
}
exit(0)
}
function is_erdos_prime(p, kf,m) {
if (!is_prime(p)) { return(0) }
kf = m = 1
while (kf < p) {
kf *= m++
if (is_prime(p-kf)) { return(0) }
}
return(1)
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
</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
Erdos primes 1-2500: 25
Erdos prime 7875: 999721
</pre>
 
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
I won't bother reproducing a primality-testing function; use the one from [[Primality_by_trial_division#FreeBASIC]].
<syntaxhighlight lang="freebasic">#include "isprime.bas"
 
function is_erdos_prime( p as uinteger ) as boolean
if not isprime(p) then return false
dim as uinteger kf=1, m=1
while kf < p
kf*=m : m+=1
if isprime(p - kf) then return false
wend
return true
end function
 
dim as integer c = 0, i = 1
while c<7875
i+=1
if is_erdos_prime(i) then
c+=1
if i<2500 or c=7875 then print c, i
end if
wend</syntaxhighlight>
{{out}}<pre>1 2
2 101
3 211
4 367
5 409
6 419
7 461
8 557
9 673
10 709
11 769
12 937
13 967
14 1009
15 1201
16 1259
17 1709
18 1831
19 1889
20 2141
21 2221
22 2309
23 2351
24 2411
25 2437
7875 999721
</pre>
 
==={{header|Palo Alto Tiny BASIC}}===
{{trans|Tiny BASIC|Removed overlapping loops.}}
Without the stretch goal because numbers are limited to signed 16-bit integers.
<syntaxhighlight lang="basic">
10 REM ERDOS-PRIMES
20 LET P=2,C=1
30 PRINT C," ",P
40 FOR P=3 TO 2500 STEP 2
50 LET Z=P;GOSUB 1000
60 IF A=0 GOTO 160
70 REM F = K!
80 LET K=1,F=1,Z=P-F
90 IF Z<0 GOTO 150
100 GOSUB 1000
110 IF A=1 GOTO 150
120 LET K=K+1,F=F*K,Z=P-F
130 IF Z<0 GOTO 150
140 GOTO 100
150 IF Z<0 LET C=C+1;PRINT C," ",P
160 NEXT P
170 STOP
980 REM PRIMALITY OF Z BY TRIAL DIVISION
990 REM RESULT IS IN A
1000 LET A=0
1010 IF Z=2 LET A=1;RETURN
1020 IF Z<3 RETURN
1030 LET Y=2
1040 IF (Z/Y)*Y=Z RETURN
1050 IF Y*Y>=Z LET A=1;RETURN
1060 LET Y=Y+1
1070 GOTO 1040
1080 RETURN
</syntaxhighlight>
{{out}}
<pre>
1 2
2 101
3 211
4 367
5 409
6 419
7 461
8 557
9 673
10 709
11 769
12 937
13 967
14 1009
15 1201
16 1259
17 1709
18 1831
19 1889
20 2141
21 2221
22 2309
23 2351
24 2411
25 2437
</pre>
 
==={{header|Tiny BASIC}}===
Can't manage the stretch goal because integers are limited to signed 16 bit.
{{works with|TinyBasic}}
Tiny BASICs other than Tom Pittman's TinyBasic use <code>,</code> instead of <code>;</code> for string concatenation in <code>PRINT</code>.
<syntaxhighlight lang="basic">10 REM Erdős-primes
20 LET P = 1
30 LET C = 0
40 IF P > 2 THEN LET P = P + 2
50 IF P < 3 THEN LET P = P + 1
60 LET Z = P
70 GOSUB 1000
80 IF A = 0 THEN GOTO 40
90 LET K = 0
100 LET F = 1
110 LET K = K + 1
120 REM F = K!
130 LET F = F * K
140 LET Z = P - F
150 IF Z < 0 THEN GOTO 190
160 GOSUB 1000
170 IF A = 1 THEN GOTO 40
180 GOTO 110
190 LET C = C + 1
200 IF P < 2500 THEN PRINT C; " "; P
210 IF P > 2500 THEN END
220 GOTO 40
990 REM primality of Z by trial division, result is in A
1000 LET Y = 1
1010 LET A = 0
1020 IF Z = 2 THEN LET A = 1
1030 IF Z < 3 THEN RETURN
1040 LET Y = Y + 1
1050 IF (Z / Y) * Y = Z THEN RETURN
1060 IF Y * Y < Z THEN GOTO 1040
1070 LET A = 1
1080 RETURN</syntaxhighlight>
{{out}}
<pre>1 2
2 101
3 211
4 367
5 409
6 419
7 461
8 557
9 673
10 709
11 769
12 937
13 967
14 1009
15 1201
16 1259
17 1709
18 1831
19 1889
20 2141
21 2221
22 2309
23 2351
24 2411
25 2437
</pre>
 
=={{header|C}}==
{{trans|Wren}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <locale.h>
 
#define LIMIT 1000000
#define LOWER_LIMIT 2500
 
bool *sieve(int limit) {
int i, p;
limit++;
// True denotes composite, false denotes prime.
bool *c = calloc(limit, sizeof(bool)); // all false by default
c[0] = true;
c[1] = true;
for (i = 4; i < limit; i += 2) c[i] = true;
p = 3; // Start from 3.
while (true) {
int p2 = p * p;
if (p2 >= limit) break;
for (i = p2; i < limit; i += 2 * p) c[i] = true;
while (true) {
p += 2;
if (!c[p]) break;
}
}
return c;
}
 
int main() {
int i, j, fact, ec = 0, ec2 = 0, lastErdos = 0;
bool found;
bool *c = sieve(LIMIT-1);
int erdos[30];
for (i = 2; i < LIMIT;) {
if (!c[i]) {
j = 1;
fact = 1;
found = true;
while (fact < i) {
if (!c[i-fact]) {
found = false;
break;
}
++j;
fact *= j;
}
if (found) {
if (i < LOWER_LIMIT) erdos[ec2++] = i;
lastErdos = i;
++ec;
}
}
i = (i > 2) ? i + 2 : i + 1;
}
setlocale(LC_NUMERIC, "");
printf("The %'d Erdős primes under %'d are:\n", ec2, LOWER_LIMIT);
for (i = 0; i < ec2; ++i) {
printf("%6d ", erdos[i]);
if (!((i+1)%10)) printf("\n");
}
printf("\n\nThe %'dth Erdős prime is %'d.\n", ec, lastErdos);
free(c);
return 0;
}</syntaxhighlight>
 
{{out}}
<pre>
The 25 Erdős primes under 2,500 are:
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 7,875th Erdős prime is 999,721.
</pre>
 
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">using System; using static System.Console;
class Program {
const int lmt = (int)1e6, first = 2500; static int[] f = new int[10];
static void Main(string[] args) {
f[0] = 1; for (int a = 0, b = 1; b < f.Length; a = b++)
f[b] = f[a] * (b + 1);
int pc = 0, nth = 0, lv = 0;
for (int i = 2; i < lmt; i++) if (is_erdos_prime(i)) {
if (i < first) Write("{0,5:n0}{1}", i, pc++ % 5 == 4 ? "\n" : " ");
nth++; lv = i; }
Write("\nCount of Erdős primes between 1 and {0:n0}: {1}\n{2} Erdős prime (the last one under {3:n0}): {4:n0}", first, pc, ord(nth), lmt, lv); }
 
static string ord(int n) {
return string.Format("{0:n0}", n) + new string[]{"th", "st", "nd", "rd", "th", "th", "th", "th", "th", "th"}[n % 10]; }
 
static bool is_erdos_prime(int p) {
if (!is_pr(p)) return false; int m = 0, t;
while ((t = p - f[m++]) > 0) if (is_pr(t)) return false;
return true;
bool is_pr(int x) {
if (x < 4) return x > 1; if ((x & 1) == 0) return false;
for (int i = 3; i * i <= x; i += 2) if (x % i == 0) return false;
return true; } } }</syntaxhighlight>
{{out}}
<pre> 2 101 211 367 409
419 461 557 673 709
769 937 967 1,009 1,201
1,259 1,709 1,831 1,889 2,141
2,221 2,309 2,351 2,411 2,437
 
Count of Erdős primes between 1 and 2,500: 25
7,875th Erdős prime (the last one under 1,000,000): 999,721</pre>
 
=={{header|C++}}==
{{libheader|Primesieve}}
<langsyntaxhighlight lang="cpp">#include <cstdint>
#include <iomanip>
#include <iostream>
Line 67 ⟶ 639:
std::wcout << L"\n\nThe " << max_count << L"th Erd\x151s prime is " << p << L".\n";
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 77 ⟶ 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>
 
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Erdős Primes. Nigel Galloway: March 22nd., 2021
let rec fN g=function 1->g |n->fN(g*n)(n-1)
Line 87 ⟶ 804:
let eP()=primes32()|>Seq.filter(fG 1>>Seq.forall id)
eP()|>Seq.takeWhile((>)2500)|>Seq.iter(printf "%d "); printfn "\n\n7875th Erdős prime is %d" (eP()|>Seq.item 7874)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 94 ⟶ 811:
7875th Erdos prime is 999721
</pre>
 
=={{header|Factor}}==
{{works with|Factor|0.99 2021-02-05}}
<syntaxhighlight lang="text">USING: formatting io kernel lists lists.lazy math
math.factorials math.primes math.primes.lists math.vectors
prettyprint sequences tools.memory.private ;
Line 112 ⟶ 830:
[ bl ] [ pprint ] interleave nl nl
 
erdős 7874 [ cdr ] timeserdős carlnth commas
"The 7,875th Erdős prime is %s.\n" printf</langsyntaxhighlight>
{{out}}
<pre>
Line 120 ⟶ 838:
 
The 7,875th Erdős prime is 999,721.
</pre>
 
=={{header|Forth}}==
{{works with|Gforth}}
<syntaxhighlight lang="forth">: prime? ( n -- ? ) here + c@ 0= ;
: notprime! ( n -- ) here + 1 swap c! ;
 
: prime_sieve { n -- }
here n erase
0 notprime!
1 notprime!
n 4 > if
n 4 do i notprime! 2 +loop
then
3
begin
dup dup * n <
while
dup prime? if
n over dup * do
i notprime!
dup 2* +loop
then
2 +
repeat
drop ;
 
: erdos_prime? { p -- ? }
p prime? if
1 1
begin
dup p <
while
p over - prime? if 2drop false exit then
swap 1+ swap
over *
repeat
2drop true
else
false
then ;
 
: print_erdos_primes { n -- }
." Erdos primes < " n 1 .r ." :" cr
n prime_sieve
0
n 0 do
i erdos_prime? if
i 5 .r
1+ dup 10 mod 0= if cr then
then
loop
cr ." Count: " . cr ;
 
2500 print_erdos_primes
bye</syntaxhighlight>
 
{{out}}
<pre>
Erdos primes < 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
Count: 25
</pre>
 
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<lang go>package main
<syntaxhighlight lang="go">package main
 
import "fmt"(
"fmt"
 
"rcu"
func sieve(limit int) []bool {
)
limit++
// True denotes composite, false denotes prime.
c := make([]bool, limit) // all false by default
c[0] = true
c[1] = true
for i := 4; i < limit; i += 2 {
c[i] = true
}
p := 3 // Start from 3.
for {
p2 := p * p
if p2 >= limit {
break
}
for i := p2; i < limit; i += 2 * p {
c[i] = true
}
for {
p += 2
if !c[p] {
break
}
}
}
return c
}
 
func commatize(n int) string {
s := fmt.Sprintf("%d", n)
if n < 0 {
s = s[1:]
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if n >= 0 {
return s
}
return "-" + s
}
 
func main() {
limit := int(1e6)
clowerLimit := sieve(limit - 1)2500
c := rcu.PrimeSieve(limit-1, true)
var erdos []int
lastErdos := 0
ec := 0
for i := 2; i < limit; {
if !c[i] {
Line 187 ⟶ 933:
}
if found {
erdosif =i append(erdos,< i)lowerLimit {
erdos = append(erdos, i)
}
lastErdos = i
ec++
}
}
Line 196 ⟶ 946:
}
}
fmt.Printf("The %d Erdős primes under %s are\n", len(erdos), rcu.Commatize(lowerLimit))
lowerLimit := 2500
rcu.PrintTable(erdos, 10, 6, false)
var erdosLower []int
fmt.Printf("\nThe %s Erdős prime is %s.\n", rcu.Commatize(ec), rcu.Commatize(lastErdos))
for _, e := range erdos {
}</syntaxhighlight>
if e < lowerLimit {
 
erdosLower = append(erdosLower, e)
{{out}}
} else {
<pre>
break
The 25 Erdős primes under 2,500 are
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 7,875 Erdős prime is 999,721.
</pre>
 
=={{header|J}}==
Implementation:
 
<syntaxhighlight lang="j">NB. erdos primes greater than !k and less than or equal to !k+1 (where !k is the factorial of k)
erdospr=: {{ k=. y
f=. !k+0 1
p=. (#~ 1= f&I.) p:(+i.)/0 1+p:inv f
p#~*/|:0=1 p:p-/!i.1+k
}}
 
NB. erdos primes less than j
erdosprs=: {{ (#~ j&>);erdospr&.>i.>.!inv j=. y }}</syntaxhighlight>
 
Task examples:
 
<syntaxhighlight lang="j"> erdosprs 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
(#,{:) erdosprs 1e6
7875 999721</syntaxhighlight>
 
=={{header|Java}}==
<syntaxhighlight lang="java">import java.util.*;
 
public class ErdosPrimes {
public static void main(String[] args) {
boolean[] sieve = primeSieve(1000000);
int maxPrint = 2500;
int maxCount = 7875;
System.out.printf("Erd\u0151s primes less than %d:\n", maxPrint);
for (int count = 0, prime = 1; count < maxCount; ++prime) {
if (erdos(sieve, prime)) {
++count;
if (prime < maxPrint) {
System.out.printf("%6d", prime);
if (count % 10 == 0)
System.out.println();
}
if (count == maxCount)
System.out.printf("\n\nThe %dth Erd\u0151s prime is %d.\n", maxCount, prime);
}
}
}
 
fmt.Printf("The %d Erdős primes under %s are\n", len(erdosLower), commatize(lowerLimit))
private static boolean erdos(boolean[] sieve, int p) {
for i, e := range erdosLower {
fmt.Printf("%6d",if e(!sieve[p])
if (i+1)%10 == 0 {return false;
for (int k = fmt.Println(1, f = 1; f < p; ++k, f *= k) {
if (sieve[p - f])
return false;
}
return true;
}
 
show := 7875
private static boolean[] primeSieve(int limit) {
fmt.Printf("\n\nThe %s Erdős prime is %s.\n", commatize(show), commatize(erdos[show-1]))
boolean[] sieve = new boolean[limit];
}</lang>
Arrays.fill(sieve, true);
if (limit > 0)
sieve[0] = false;
if (limit > 1)
sieve[1] = false;
for (int i = 4; i < limit; i += 2)
sieve[i] = false;
for (int p = 3; ; p += 2) {
int q = p * p;
if (q >= limit)
break;
if (sieve[p]) {
int inc = 2 * p;
for (; q < limit; q += inc)
sieve[q] = false;
}
}
return sieve;
}
}</syntaxhighlight>
 
{{out}}
<pre>
The 25 Erdős primes underless 2,500than are2500:
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 7,8757875th Erdős prime is 999,721999721.
</pre>
 
=={{header|Phixjq}}==
{{works with|jq}}
<lang Phix>atom t0 = time()
'''Works with gojq, the Go implementation of jq''' (but the second task requires an unreasonable amount of memory)
sequence facts = {1}
 
function erdos(integer p)
 
while facts[$]<p do
'''Preliminaries'''
facts &= facts[$]*(length(facts)+1)
<syntaxhighlight lang="jq">def emit_until(cond; stream): label $out | stream | if cond then break $out else . end;
end while
 
for i=length(facts) to 1 by -1 do
def is_prime:
integer pmk = p-facts[i]
. as $n
if pmk>0 then
| if ($n < 2) if is_prime(pmk) then return false end if
elif ($n % 2 end== if0) then $n == 2
elif ($n % 3 == 0) then $n == 3
end for
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
else 23
| until( (. * .) > $n or ($n % . == 0); . + 2)
| . * . > $n
end;
</syntaxhighlight>
'''Erdős-primes'''
<syntaxhighlight lang="jq">
def is_Erdos:
. as $p
| if is_prime|not then false
else label $out
| foreach range(1; .+1) as $k (1; . * $k;
if . >= $p then true, break $out
elif ($p - .) | is_prime then 0, break $out
else empty
end) // true
| . == true
end ;
 
# emit the Erdos primes
def Erdos: range(2; infinite) | select(is_Erdos);
</syntaxhighlight>
'''The tasks'''
<syntaxhighlight lang="jq">"The Erdős primes less than 2500 are:", emit_until(. >= 2500; Erdos),
 
"\nThe 7875th Erdős prime is \(nth(7874; Erdos))."
</syntaxhighlight>
{{out}}
<pre>
The Erdős primes less than 2500 are:
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 Erdős prime is 999721.
</pre>
 
=={{header|Julia}}==
<syntaxhighlight lang="julia">using Primes, Formatting
 
function isErdős(p::Integer)
isprime(p) || return false
for i in 1:100
kfac = factorial(i)
kfac >= p && break
isprime(p - kfac) && return false
end
return true
end function
 
sequence res = filter(get_primes_le(2500),erdos)
const Erdőslist = filter(isErdős, 1:1000000)
printf(1,"Found %d Erdos primes < 2,500:\n%s\n\n",{length(res),join(apply(res,sprint))})
resconst E2500 = filter(get_primes_le(1000000)x -> x < 2500,erdos Erdőslist)
 
integer l = length(res)
println(length(E2500), " Erdős primes < 2500: ", E2500)
printf(1,"The %,d%s Erdos prime is %,d (%s)\n",{l,ord(l),res[$],elapsed(time()-t0)})</lang>
println("The 7875th Erdős prime is ", format(Erdőslist[7875], commas=true))
</syntaxhighlight>{{out}}
<pre>
25 Erdős primes < 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]
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}}==
<syntaxhighlight lang="mathematica">ClearAll[ErdosPrimeQ]
ErdosPrimeQ[p_Integer] := Module[{k},
If[PrimeQ[p],
k = 1;
While[k! < p,
If[PrimeQ[p - k!], Return[False]];
k++;
];
True
,
False
]
]
sel = Select[Range[2500], ErdosPrimeQ]
Length[sel]
sel = Select[Range[999999], ErdosPrimeQ];
{Length[sel], Last[sel]}</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}
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}}==
<syntaxhighlight lang="nim">import math, sets, strutils, sugar
 
const N = 1_000_000
 
# Sieve of Erathostenes.
var isComposite: array[2..N, bool]
for n in 2..N:
let n2 = n * n
if n2 > N: break
if not isComposite[n]:
for k in countup(n2, N, n):
isComposite[k] = true
 
template isPrime(n: int): bool = n > 1 and not isComposite[n]
 
let primeList = collect(newSeq):
for n in 2..N:
if n.isPrime: n
 
const Factorials = collect(newSeq):
for n in 1..20:
if fac(n) >= N: break
fac(n)
 
 
proc isErdösPrime(p: int): bool =
## Check if prime "p" is an Erdös prime.
for f in Factorials:
if f >= p: break
if (p - f).isPrime: return false
result = true
 
 
let erdösList2500 = collect(newSeq):
for p in primeList:
if p >= 2500: break
if p.isErdösPrime: p
 
echo "Found $# Erdös primes less than 2500:".format(erdösList2500.len)
for i, prime in erdösList2500:
stdout.write ($prime).align(5)
stdout.write if (i+1) mod 10 == 0: '\n' else: ' '
echo()
 
var erdös7875: int
var count = 0
for p in primeList:
if p.isErdösPrime: inc count
if count == 7875:
erdös7875 = p
break
echo "\nThe 7875th Erdös prime is $#.".format(erdös7875)</syntaxhighlight>
 
{{out}}
<pre>Found 25 Erdös 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
 
The 7875th Erdös prime is 999721.</pre>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
use utf8;
binmode(STDOUT, ':utf8');
use List::AllUtils 'before';
use ntheory qw<is_prime factorial>;
 
sub is_erdos {
my($n) = @_; my $k;
return unless is_prime($n);
while ($n > factorial($k++)) { return if is_prime $n-factorial($k) }
'True'
}
 
my(@Erdős,$n);
do { push @Erdős, $n if is_erdos(++$n) } until $n >= 1e6;
 
say 'Erdős primes < ' . (my $max = 2500) . ':';
say join ' ', before { $_ > 2500 } @Erdős;
say "\nErdős prime #" . @Erdős . ' is ' . $Erdős[-1];</syntaxhighlight>
{{out}}
<pre>Erdős primes < 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
 
Erdős prime #7875 is 999721</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">-->
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">facts</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">erdos</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">facts</span><span style="color: #0000FF;">[$]<</span><span style="color: #000000;">p</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">facts</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">facts</span><span style="color: #0000FF;">[$]*(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">facts</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">facts</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pmk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">-</span><span style="color: #000000;">facts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pmk</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pmk</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2500</span><span style="color: #0000FF;">),</span><span style="color: #000000;">erdos</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Found %d Erdos primes &lt; 2,500:\n%s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">))})</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000000</span><span style="color: #0000FF;">),</span><span style="color: #000000;">erdos</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The %,d%s Erdos prime is %,d (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[$],</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 252 ⟶ 1,387:
 
The 7,875th Erdos prime is 999,721 (1.2s)
</pre>
 
=={{header|PL/0}}==
Without stretch goal.
<syntaxhighlight lang="pascal">
var p, c, z, k, isprime, factk, iskchecked;
 
procedure checkprimality;
var i, isichecked;
begin
isprime := 0;
if z = 2 then isprime := 1;
if z >= 3 then
begin
i := 2; isichecked := 0;
while isichecked = 0 do
begin
if (z / i) * i = z then isichecked := 1;
if isichecked = 0 then
if i * i >= z then
begin
isprime := 1; isichecked := 1
end;
i := i + 1
end
end
end;
 
begin
p := 2; c := 1;
! p;
p := 3;
while p <= 2500 do
begin
z := p; call checkprimality;
if isprime = 1 then
begin
k := 1; factk := 1; z := p - factk;
iskchecked := 1;
if z >= 0 then iskchecked := 0;
while iskchecked = 0 do
begin
call checkprimality;
if isprime = 1 then iskchecked := 1;
if isprime <> 1 then
begin
k := k + 1; factk := factk * k; z := p - factk;
iskchecked := 1;
if z >= 0 then iskchecked := 0
end
end;
if z < 0 then
begin
c := c + 1;
! p
end
end;
p := p + 2
end
end.
</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>
 
=={{header|PL/M}}==
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
Basic task only as PL/M integers are 8/16 bit unsigned.
<syntaxhighlight lang="plm">
100H: /* FIND ERDOS PRIMES: PRIMES P WHERE P-K! IS COMPOSITE FOR ALL 1<=K!<P */
 
/* CP/M SYSTEM CALL AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;
PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
 
/* TASK */
 
DECLARE MAX$NUMBER LITERALLY '2500'
, FALSE LITERALLY '0'
, TRUE LITERALLY '0FFH'
;
 
DECLARE PRIME ( MAX$NUMBER )BYTE; /* SIEVE THE PRIMES TO MAX$NUMBER - 1 */
DECLARE I ADDRESS;
PRIME( 0 ), PRIME( 1 ) = FALSE;
PRIME( 2 ) = TRUE;
DO I = 3 TO LAST( PRIME ) BY 2; PRIME( I ) = TRUE; END;
DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END;
DO I = 3 TO LAST( PRIME ) BY 2;
IF PRIME( I ) THEN DO;
DECLARE S ADDRESS;
DO S = I + I TO LAST( PRIME ) BY I;
PRIME( S ) = FALSE;
END;
END;
END;
 
/* TABLE OF FACTORIALS */
DECLARE FACTORIAL ( 8 )ADDRESS INITIAL( 1, 1, 2, 6, 24, 120, 720, 5040 );
 
/* RETURNS TRUE IF P IS AN ERDOS PRIME, FALSE OTHERWISE */
IS$ERDOS$PRIME: PROCEDURE( P )BYTE;
DECLARE P ADDRESS;
DECLARE RESULT BYTE;
RESULT = PRIME( P );
IF RESULT THEN DO;
DECLARE K BYTE;
K = 1;
DO WHILE FACTORIAL( K ) < P AND RESULT;
RESULT = NOT PRIME( P - FACTORIAL( K ) );
K = K + 1;
END;
END;
RETURN RESULT;
END IS$ERDOS$PRIME ;
 
/* FIND THE ERDOS PRIMES */
DECLARE ( P, COUNT ) ADDRESS;
COUNT = 0;
IF IS$ERDOS$PRIME( 2 ) THEN DO;
COUNT = COUNT + 1;
CALL PR$STRING( .' 2$' );
END;
P = 1;
DO WHILE COUNT < 25;
P = P + 2;
IF IS$ERDOS$PRIME( P ) THEN DO;
COUNT = COUNT + 1;
CALL PR$CHAR( ' ' );
IF P < 1000 THEN CALL PR$CHAR( ' ' );
CALL PR$NUMBER( P );
IF COUNT MOD 5 = 0 THEN CALL PR$NL;
END;
END;
 
EOF
</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>
 
=={{header|Raku}}==
 
<syntaxhighlight lang="raku" perl6line>use Lingua::EN::Numbers;
 
my @factorial = 1, |[\*] 1..*;
Line 263 ⟶ 1,581:
put 'Erdős primes < 2500:';
put @Erdős[^(@Erdős.first: * > 2500, :k)]».&comma;
put "\nThe 7,875th Erdős prime is: " ~ @Erdős[7874].&comma;</langsyntaxhighlight>
{{out}}
<pre>Erdős primes < 2500:
Line 269 ⟶ 1,587:
 
The 7,875th Erdős prime is: 999,721</pre>
 
Alternately, using fewer hard coded values:
 
 
<syntaxhighlight lang="raku" line>use Lingua::EN::Numbers;
use List::Divvy;
 
my @factorial = 1, |[\*] 1..*;
my @Erdős = ^∞ .grep: { .is-prime and none($_ «-« @factorial.&upto: $_).is-prime }
 
put "Erdős primes < 2500:\n" ~ @Erdős.&before(2500)».&comma.batch(8)».fmt("%5s").join: "\n";
put "\nThe largest Erdős prime less than {comma 1e6.Int} is {comma .[*-1]} in {.&ordinal-digit} position."
given @Erdős.&before(1e6);</syntaxhighlight>
{{out}}
<pre>Erdős primes < 2500:
2 101 211 367 409 419 461 557
673 709 769 937 967 1,009 1,201 1,259
1,709 1,831 1,889 2,141 2,221 2,309 2,351 2,411
2,437
 
The largest Erdős prime less than 1,000,000 is 999,721 in 7875th position.</pre>
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX program counts/displays the number of Erdos primes under a specified number N. */
parse arg n cols . /*get optional number of primes to find*/
if n=='' | n=="," then n= 2500 /*Not specified? Then assume default.*/
Line 278 ⟶ 1,617:
call genP n /*generate all primes under N. */
w= 10 /*width of a number in any column. */
if cols>0 then say ' index │'center(" Erdos primes that are < " n, 1 + cols*(w+1) )
if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─')
call facts /*generate a table of needed factorials*/
Eprimes= 0; idx= 1 idx= 1 /*initialize # of additive primes & idx*/
$= /*a list of additive primes (so far). */
do j=21 untilfor j>=n#; if \! prime= @.j then iterate /*Is J not a prime? No, then skip it. */
do k=1 until fact.k>j /*verify: J-K! for 1≤K!<J are composite*/
z= jprime - fact.k /*subtract some factorial from a prime.*/
if !.z then iterate j /*Is Z is a prime? Then skip it. */
end /*j*/
 
Eprimes= Eprimes + 1; EprimeL= j /*bump the count of Erdos primes. */
if cols==<0 then iterate /*Build the list (to be shown later)? */
c= commas(j) /*maybe add some commas to the number. */
c= commas(j)
$= $ right(c, max(w, length(c) ) ) /*add Erdos prime to list, allow big #.*/
if Eprimes//cols\==0 then iterate /*have we populated a line of output? */
Line 299 ⟶ 1,638:
 
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─')
say
say 'found ' commas(Eprimes) " Erdos primes < " commas(n)
Line 320 ⟶ 1,660:
end /*k*/ /* [↑] only divide up to √ J */
#= # + 1; @.#= j; !.j= 1 /*bump prime count; assign prime & flag*/
end /*j*/; return</syntaxhighlight>
return</lang>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 329 ⟶ 1,668:
11 │ 769 937 967 1,009 1,201 1,259 1,709 1,831 1,889 2,141
21 │ 2,221 2,309 2,351 2,411 2,437
───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────
 
found 25 Erdos primes < 2500
</pre>
 
{{out|output|text=&nbsp; when using the inputs ifof: &nbsp; &nbsp; <tt> 1000000 &nbsp; 0 </tt>}}
<pre>
found 7,875 Erdos primes < 1,000,000
 
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>
 
=={{header|Rust}}==
<syntaxhighlight lang="rust">// [dependencies]
// primal = "0.3"
 
use std::collections::HashSet;
 
fn erdos_primes() -> impl std::iter::Iterator<Item = usize> {
let mut primes = HashSet::new();
let mut all_primes = primal::Primes::all();
std::iter::from_fn(move || {
'all_primes: for p in all_primes.by_ref() {
primes.insert(p);
let mut k = 1;
let mut f = 1;
while f < p {
if primes.contains(&(p - f)) {
continue 'all_primes;
}
k += 1;
f *= k;
}
return Some(p);
}
None
})
}
 
fn main() {
let mut count = 0;
println!("Erd\u{151}s primes less than 2500:");
for p in erdos_primes().take_while(|x| *x < 2500) {
count += 1;
if count % 10 == 0 {
println!("{:4}", p);
} else {
print!("{:4} ", p);
}
}
println!();
if let Some(p) = erdos_primes().nth(7874) {
println!("\nThe 7875th Erd\u{151}s prime is {}.", p);
}
}</syntaxhighlight>
 
{{out}}
<pre>
Erdős 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
 
The 7875th Erdős prime is 999721.
</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) {
 
return true if p==2
return false if !p.is_prime
 
var f = 1
 
for (var k = 2; f < p; k++) {
p - f -> is_composite || return false
f *= k
}
 
return true
}
 
say ("Erdős primes <= 2500: ", 1..2500 -> grep(is_erdos_prime))
say ("The 7875th Erdős prime is: ", is_erdos_prime.nth(7875))</syntaxhighlight>
{{out}}
<pre>
Erdős primes <= 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]
The 7875th Erdős prime is: 999721
</pre>
 
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
import "./seqfmt" for LstFmt
import "/fmt" for Fmt
 
var limit = 1e6
var lowerLimit = 2500
var primes = Int.primeSieve(limit - 1, true)
var c = Int.primeSieve(limit - 1, false)
var erdos = []
var lastErdos = 0
for (p in primes) {
var iec = 10
var facti = 12
while (i < limit) {
var found = true
whileif (fact < p!c[i]) {
ifvar (Int.isPrime(pj -= fact)) {1
var foundfact = false1
var found = breaktrue
while (fact < i) {
if (!c[i - fact]) {
found = false
break
}
j = j + 1
fact = fact * j
}
if (found) {
if (i < lowerLimit) erdos.add(i)
lastErdos = i
ec = ec + 1
}
i = i + 1
fact = fact * i
}
i = (i > 2) ? i + 2 : i + 1
if (found) erdos.add(p)
}
 
var lowerLimit = 2500
Fmt.print("The $,d Erdős primes under $,d are:", erdos.count, lowerLimit)
var erdosLower = erdos.where { |e| e < lowerLimit}.toList
Fmt.tprint("$6d", erdos, 10)
Fmt.print("The $,d Erdős primes under $,d are:", erdosLower.count, lowerLimit)
Fmt.print("\nThe $,r Erdős prime is $,d.", ec, lastErdos)</syntaxhighlight>
for (chunk in Lst.chunks(erdosLower, 10)) Fmt.print("$6d", chunk)
var show = 7875
Fmt.print("\nThe $,r Erdős prime is $,d.", show, erdos[show-1])</lang>
 
{{out}}
<pre>
The 25 Erdős primes under 2,500 are:
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 7,875th Erdős prime is 999,721.
</pre>
 
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is prime
int N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false;
I:= I+1;
];
return true;
];
 
func Erdos(N); \Return 'true' if N is an Erdos prime
int N, F, K;
[if not IsPrime(N) then return false;
F:= 1; K:= 1;
while F < N do
[if IsPrime(N-F) then return false;
K:= K+1; F:= F*K;
];
return true;
];
 
int Cnt, N, SN;
[Format(5, 0);
Cnt:= 0; N:= 2;
repeat if Erdos(N) then
[RlOut(0, float(N));
Cnt:= Cnt+1;
if rem(Cnt/10) = 0 then CrLf(0);
];
N:= N+1;
until N >= 2500;
CrLf(0);
Text(0, "Found "); IntOut(0, Cnt); Text(0, " Erdos primes^m^j");
Cnt:= 1; N:= 3;
repeat if Erdos(N) then [Cnt:= Cnt+1; SN:= N];
N:= N+2;
until N >= 1_000_000;
Text(0, "The "); IntOut(0, Cnt);
Text(0, "th Erdos prime is indeed "); IntOut(0, SN); CrLf(0);
]</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
Found 25 Erdos primes
The 7875th Erdos prime is indeed 999721
</pre>
Not a robot
2,099

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/309569...363433"