Erdős-primes

From Rosetta Code
Task
Erdős-primes
You are encouraged to solve this task according to the task description, using any language you may know.
Definitions

In mathematics, Erdős primes are prime numbers such that all p-k! for 1<=k!<p are composite.

Task

Write a program to determine (and show here) all Erdős primes less than 2500.

Optionally, show the number of Erdős primes.

Stretch goal

Show that the 7,875th Erdős prime is 999,721 (the highest below 1,000,000)

Also see



11l

Translation of: Nim
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
Output:
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.

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`."/
Output:
     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.

Action!

Library: Action! Sieve of Eratosthenes
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
Output:

Screenshot from Atari 8-bit computer 

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

ALGOL 68 

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
Output:
  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

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'
}
Output:
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

Arturo 

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]
Output:
    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

AWK

Translation of: FreeBASIC
# 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)
}
Output:
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

BASIC

FreeBASIC

I won't bother reproducing a primality-testing function; use the one from Primality_by_trial_division#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
Output:
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

Palo Alto Tiny BASIC

Translation of: Tiny BASIC – Removed overlapping loops.

Without the stretch goal because numbers are limited to signed 16-bit integers. 

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
Output:
      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

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 , instead of ; for string concatenation in PRINT. 

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
Output:
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

C

Translation of: Wren
#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;
}
Output:
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.

C# 

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; } } }
Output:
    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

C++

Library: Primesieve
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <set>
#include <primesieve.hpp>

class erdos_prime_generator {
public:
    erdos_prime_generator() {}
    uint64_t next();
private:
    bool erdos(uint64_t p) const;
    primesieve::iterator iter_;
    std::set<uint64_t> primes_;
};

uint64_t erdos_prime_generator::next() {
    uint64_t prime;
    for (;;) {
        prime = iter_.next_prime();
        primes_.insert(prime);
        if (erdos(prime))
            break;
    }
    return prime;
}

bool erdos_prime_generator::erdos(uint64_t p) const {
    for (uint64_t k = 1, f = 1; f < p; ++k, f *= k) {
        if (primes_.find(p - f) != primes_.end())
            return false;
    }
    return true;
}

int main() {
    std::wcout.imbue(std::locale(""));
    erdos_prime_generator epgen;
    const int max_print = 2500;
    const int max_count = 7875;
    uint64_t p;
    std::wcout << L"Erd\x151s primes less than " << max_print << L":\n";
    for (int count = 1; count <= max_count; ++count) {
        p = epgen.next();
        if (p < max_print)
            std::wcout << std::setw(6) << p << (count % 10 == 0 ? '\n' : ' ');
    }
    std::wcout << L"\n\nThe " << max_count << L"th Erd\x151s prime is " << p << L".\n";
    return 0;
}
Output:
Erdős primes less than 2,500:
     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 7,875th Erdős prime is 999,721.

Delphi

Works with: Delphi version 6.0
Library: SysUtils,StdCtrls

Executes in 225 ms. It could be faster with a Factorial lookup table. 

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;
Output:
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


EasyLang

Translation of: Action!
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 & " "
   .
.
Output:
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

F#

This task uses Extensible Prime Generator (F#) 

// Erdős Primes. Nigel Galloway: March 22nd., 2021
let rec fN g=function 1->g |n->fN(g*n)(n-1)
let rec fG n g=seq{let i=fN 1 n in if i<g then yield (isPrime>>not)(g-i); yield! fG(n+1) g}
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)
Output:
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

7875th Erdos prime is 999721

Factor

Works with: Factor version 0.99 2021-02-05
USING: formatting io kernel lists lists.lazy math
math.factorials math.primes math.primes.lists math.vectors
prettyprint sequences tools.memory.private ;

: facts ( -- list ) 1 lfrom [ n! ] lmap-lazy ;

: n!< ( p -- seq ) [ facts ] dip [ < ] curry lwhile list>array ;

: erdős? ( p -- ? ) dup n!< n-v [ prime? ] none? ;

: erdős ( -- list ) lprimes [ erdős? ] lfilter ;

erdős [ 2500 < ] lwhile list>array
dup length "Found  %d  Erdős primes < 2500:\n" printf
[ bl ] [ pprint ] interleave nl nl

7874 erdős lnth commas
"The 7,875th Erdős prime is %s.\n" printf
Output:
Found  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 7,875th Erdős prime is 999,721.

Forth

Works with: Gforth
: 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
Output:
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

Go

Translation of: Wren
Library: Go-rcu
package main

import (
    "fmt"
    "rcu"
)

func main() {
    limit := int(1e6)
    lowerLimit := 2500
    c := rcu.PrimeSieve(limit-1, true)
    var erdos []int
    lastErdos := 0
    ec := 0
    for i := 2; i < limit; {
        if !c[i] {
            found := true
            for j, fact := 1, 1; fact < i; {
                if !c[i-fact] {
                    found = false
                    break
                }
                j++
                fact = fact * j
            }
            if found {
                if i < lowerLimit {
                    erdos = append(erdos, i)
                }
                lastErdos = i
                ec++
            }
        }
        if i > 2 {
            i += 2
        } else {
            i += 1
        }
    }
    fmt.Printf("The %d Erdős primes under %s are\n", len(erdos), rcu.Commatize(lowerLimit))
    rcu.PrintTable(erdos, 10, 6, false)
    fmt.Printf("\nThe %s Erdős prime is %s.\n", rcu.Commatize(ec), rcu.Commatize(lastErdos))
}
Output:
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.

J

Implementation: 

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 }}

Task examples: 

   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

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);
            }
        }
    }

    private static boolean erdos(boolean[] sieve, int p) {
        if (!sieve[p])
            return false;
        for (int k = 1, f = 1; f < p; ++k, f *= k) {
            if (sieve[p - f])
                return false;
        }
        return true;
    }

    private static boolean[] primeSieve(int limit) {
        boolean[] sieve = new boolean[limit];
        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;
    }
}
Output:
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.

jq

Works with: jq

Works with gojq, the Go implementation of jq (but the second task requires an unreasonable amount of memory)


Preliminaries 

def emit_until(cond; stream): label $out | stream | if cond then break $out else . end;

def is_prime:
  . as $n
  | if ($n < 2)         then false
    elif ($n % 2 == 0)  then $n == 2
    elif ($n % 3 == 0)  then $n == 3
    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;

Erdős-primes 

 
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);

The tasks 

"The Erdős primes less than 2500 are:", emit_until(. >= 2500; Erdos),

"\nThe 7875th Erdős prime is \(nth(7874; Erdos))."
Output:
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.

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

const Erdőslist = filter(isErdős, 1:1000000)
const E2500 = filter(x -> x < 2500, Erdőslist)

println(length(E2500), " Erdős primes < 2500: ", E2500)
println("The 7875th Erdős prime is ", format(Erdőslist[7875], commas=true))
Output:
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

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)
Output:
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

Mathematica /Wolfram Language 

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]}
Output:
{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}

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)]]
Output:
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

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)
Output:
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.

Perl

Library: ntheory
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];
Output:
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

Phix 

atom t0 = time()
sequence facts = {1}
function erdos(integer p)
    while facts[$]<p do
        facts &= facts[$]*(length(facts)+1)
    end while
    for i=length(facts) to 1 by -1 do
        integer pmk = p-facts[i]
        if pmk>0 then
            if is_prime(pmk) then return false end if
        end if
    end for
    return true
end function
sequence res = filter(get_primes_le(2500),erdos)
printf(1,"Found %d Erdos primes < 2,500:\n%s\n\n",{length(res),join(apply(res,sprint))})
res = filter(get_primes_le(1000000),erdos)
integer l = length(res)
printf(1,"The %,d%s Erdos prime is %,d (%s)\n",{l,ord(l),res[$],elapsed(time()-t0)})
Output:
Found 25 Erdos primes < 2,500:
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 Erdos prime is 999,721 (1.2s)

PL/0

Without stretch goal. 

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.
Output:
       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

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. 

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
Output:
    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

Python 

def factorial(n):
    if n-1 < len(factorials):
        return factorials[n - 1]
    total = 1
    for i in range(1, n + 1):
        total *= i
    factorials.append(total)
    return total

def prime(n):
    for y in p:
        if n % y == 0:
            return False
        if y > int(n ** 0.5):
            return True

def erdos(pr):
    sub = 1
    while factorial(sub) <= pr:
        if pr - factorial(sub) in p:
            return False
        else:
            sub += 1
    return True

factorials = []
stopper = 0
x = -1
counter = 0
list = []
p = [2]
coeff = -1


while counter < 7875:
    x += 1
    if x < len(p):
        if erdos(p[x]) == True:
            if p[x] < 2500:
                print(p[x])
            if p[x] > 2500 and stopper == 0:
                print(f'There are {counter} Erdos primes less than 2500')
                stopper = 1
            counter += 1
    else:
        coeff += 1
        for i in range(coeff * 10000 + 2, (coeff + 1) * 10000 + 2):
            if prime(i) == True:
                p.append(i)
        x -= 1

print(f'The {counter}th Erdos prime is {p[x]}')
Output:
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 less than 2500
The 7875th Erdos prime is 999721

Raku 

use Lingua::EN::Numbers;

my @factorial = 1, |[\*] 1..*;
my @Erdős = ^Inf .grep: { .is-prime and none($_ «-« @factorial[^(@factorial.first: * > $_, :k)]).is-prime }

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;
Output:
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 7,875th Erdős prime is: 999,721

Alternately, using fewer hard coded values: 


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);
Output:
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.

REXX

Version 1

/*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.*/
if cols=='' | cols==","  then cols=   10         /* "      "          "     "       "   */
nn= n;                           n= abs(n)       /*N<0:  shows highest Erdos prime< │N│ */
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           /*initialize # of additive primes & idx*/
$=                                               /*a list of additive primes  (so far). */
     do j=1  for #;             prime= @.j       /*                                     */
        do k=1  until fact.k>j                   /*verify: J-K! for 1≤K!<J are composite*/
        z= prime - 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. */
     $= $ 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?  */
     say center(idx, 7)'│'  substr($, 2);   $=   /*display what we have so far  (cols). */
     idx= idx + cols                             /*bump the  index  count for the output*/
     end   /*j*/

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)
say
if nn<0  then say commas(EprimeL)  ' is the '  commas(Eprimes)th(Eprimes)  " Erdos prime."
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?;  do jc=length(?)-3  to 1  by -3; ?=insert(',', ?, jc); end;  return ?
facts:  arg x; fact.=1;  do x=2 until fact.x>1e9; p= x-1; fact.x= x*fact.p; end;  return
th:     parse arg th; return word('th st nd rd', 1+(th//10) *(th//100%10\==1) *(th//10<4))
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: parse arg n;   @.=.; @.1=2;  @.2=3;  @.3=5;  @.4=7;  @.5=11;  @.6=13;  @.7=17;  #= 7
      w= length(n);  !.=0; !.2=1;  !.3=1;  !.5=1;  !.7=1;  !.11=1;  !.13=1;  !.17=1
            do j=@.7+2  by 2  while j<n          /*continue on with the next odd prime. */
            parse var  j  ''  -1  _              /*obtain the last digit of the  J  var.*/
            if _      ==5  then iterate          /*is this integer a multiple of five?  */
            if j // 3 ==0  then iterate          /* "   "     "    "     "     " three? */
                                                 /* [↓]  divide by the primes.   ___    */
                  do k=4  to #  while  k*k<=j    /*divide  J  by other primes ≤ √ J     */
                  if j//@.k == 0  then iterate j /*÷ by prev. prime?  ¬prime     ___    */
                  end   /*k*/                    /* [↑]   only divide up to     √ J     */
            #= # + 1;          @.#= j;  !.j= 1   /*bump prime count; assign prime & flag*/
            end   /*j*/;                return
output   when using the default inputs:
 index │                                         Erdos primes that are  <  2500
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          2        101        211        367        409        419        461        557        673        709
  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
output   when using the inputs of:     1000000   0 
found  7,875  Erdos primes  <  1,000,000

999,721  is the  7,875th  Erdos prime.
30 seconds

Version 2

Libraries: How to use
Library: Functions
Library: Numbers

say 'Erdos primes - Using REXX libraries - Build 20240829'
parse version version; say version; say

/* Primes is in Numbers: See Extensible prime generator */
/* Fact is in Functions: See Factorial */

call Time('r'); numeric digits 5
call Primes 2500
call Task 2500
say; say Format(Time('e'),,3) 'seconds'; say

call Time('r'); numeric digits 7
call Primes 1000000
call Stretch 7875
say; say Format(Time('e'),,3) 'seconds'; say
exit

Task:
procedure expose prim. flag. fact.
arg x
say 'Erdos primes <' x':'
n = 0; fact. = 0
do i = 1 to prim.0
   a = prim.prime.i
   do j = 1
      k = Fact(j)
      if k >= a then
         leave
      p = a-k
      if flag.prime.p then
         iterate i
   end
   n = n+1
   call Charout ,Right(a,5)
   if n//10 = 0 then
      say
end
say; say n 'Erdos primes found'
return

Stretch:
procedure expose prim. flag. fact.
arg x
say x'th Erdos prime:'
n = 0; fact. = 0
do i = 1 to prim.0
   a = prim.prime.i
   do j = 1
      k = Fact(j)
      if k >= a then
         leave j
      p = a-k
      if flag.prime.p then
         iterate i
   end
   n = n+1
   if n = x then do
      say a
      leave i
   end
end
say x 'Erdos primes processed'
return

include Functions
include Numbers
Output:
Erdos primes - Using REXX libraries - Build 20240829
REXX-ooRexx_5.0.0(MT)_64-bit 6.05 23 Dec 2022

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
25 Erdos primes found

0.016 seconds

7875th Erdos prime:
999721
7875 Erdos primes processed

1.906 seconds

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
Output:
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...

RPL

Works with: HP version 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?
» » 'ERDOS?' STO      @  ( n → erdös(n) )

« { } 2
  WHILE DUP 2500 < REPEAT
     IF DUP ERDOS? THEN SWAP OVER + SWAP END
     NEXTPRIME
  END 
  DROP DUP SIZE "count" →TAG
 » 'TASK' STO        @   ( → results )
Output:
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.

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);
    }
}
Output:
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.

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;
Output:
     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

Sidef 

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))
Output:
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

Wren

Library: Wren-math
Library: Wren-fmt
import "./math" for Int
import "./fmt" for Fmt

var limit = 1e6
var lowerLimit = 2500
var c = Int.primeSieve(limit - 1, false)
var erdos = []
var lastErdos = 0
var ec = 0
var i = 2
while (i < limit) {
    if (!c[i]) {
        var j = 1
        var fact = 1
        var found = true
        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 > 2) ? i + 2 : i + 1
}

Fmt.print("The $,d Erdős primes under $,d are:", erdos.count, lowerLimit)
Fmt.tprint("$6d", erdos, 10)
Fmt.print("\nThe $,r Erdős prime is $,d.", ec, lastErdos)
Output:
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.

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);
]
Output:
    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
Retrieved from "https://rosettacode.org/wiki/Erdős-primes?oldid=369347"