Erdős-primes: Difference between revisions
(Replaced with correct task description) |
(added Phix) |
||
| Line 15: | Line 15: | ||
:* the OEIS entry: [http://oeis.org/A064152 A064152 Erdos primes]. |
:* the OEIS entry: [http://oeis.org/A064152 A064152 Erdos primes]. |
||
<br><br> |
<br><br> |
||
=={{header|Phix}}== |
|||
<lang 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)})</lang> |
|||
{{out}} |
|||
<pre> |
|||
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) |
|||
</pre> |
|||
Revision as of 20:29, 19 March 2021
- Definitions
In mathematics, Erdős primes are prime numbers such that all p-k! for 1<=k!<p are composite. 2
- Task
Write a program to determine (and show here) all Erdős primes whose elements are less than 2500.
Optionally, show the number of Erdős primes.
- Stretch goal
Show that the 7875th Erdős prime is 999721
- Also see
-
- the OEIS entry: A064152 Erdos primes.
Phix
<lang Phix>atom t0 = time() sequence facts = {1} function erdos(integer p)
while facts[$]
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)})</lang>
- 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)