Anonymous user
Erdős-primes: Difference between revisions
→{{header|Nim}}
Catskill549 (talk | contribs) (added AWK) |
|||
Line 477:
The 7875th Erdős prime is 999,721
</pre>
=={{header|Nim}}==
<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)</lang>
{{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}}==
| |||