Anonymous user
Primorial numbers: Difference between revisions
→{{header|Nim}}
MaiconSoft (talk | contribs) (Added Delphi exemple) |
|||
Line 1,693:
primorial(10000) has 45337 digits, in 128ms
primorial(100000) has 563921 digits, in 12304ms</pre>
=={{header|Nim}}==
{{libheader|bignum}}
We use a sieve of Erathosthenes to generate the primes, but with only the odd numbers to reduce memory usage. Even for one millions primes, the execution time is negligible (0.12s)
To compute the primorial numbers, we use an iterator. Performance is good with 1.1s for primorial(10000). But for one million, this takes much more time.
<lang Nim>import times
let t0 = cpuTime()
####################################################################################################
# Build list of primes.
const
NPrimes = 1_000_000
N = 16 * NPrimes
var sieve: array[(N - 1) div 2 + 1, bool] # False (default) means prime.
for i, composite in sieve:
if not composite:
let n = 2 * i + 3
for k in countup(n * n, N, 2 * n):
sieve[(k - 3) div 2] = true
var primes = @[2]
for i, composite in sieve:
if not composite:
primes.add 2 * i + 3
if primes.len < NPrimes:
quit "Not enough primes. Please, increase value of N."
####################################################################################################
# Compute primorial.
import strformat
import bignum
const LastToPrint = NPrimes
iterator primorials(): Int =
## Yield successive primorial numbers.
var prim = newInt(1)
yield prim
for p in primes:
prim *= p
yield prim
var n = 0
for prim in primorials():
echo &"primorial({n}) = {prim}"
inc n
if n == 10: break
n = 0
var nextToPrint = 10
for prim in primorials():
if n == nextToPrint:
echo &"primorial({n}) has {($prim).len} digits"
if nextToPrint == LastToPrint: break
nextToPrint *= 10
inc n
echo ""
echo &"Total time: {cpuTime() - t0:.2f} s"</lang>
{{out}}
<pre>primorial(0) = 1
primorial(1) = 2
primorial(2) = 6
primorial(3) = 30
primorial(4) = 210
primorial(5) = 2310
primorial(6) = 30030
primorial(7) = 510510
primorial(8) = 9699690
primorial(9) = 223092870
primorial(10) has 10 digits
primorial(100) has 220 digits
primorial(1000) has 3393 digits
primorial(10000) has 45337 digits
primorial(100000) has 563921 digits
primorial(1000000) has 6722809 digits
Total time: 127.65 s</pre>
CPU: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz, 2607 MHz with 8GB RAM.
=={{header|PARI/GP}}==
| |||