Anonymous user
Twin primes: Difference between revisions
→{{header|Kotlin}}
Catskill549 (talk | contribs) |
|||
Line 731:
return true
}</lang>
=={{header|Nim}}==
We use a sieve of Erathostenes which needs a lot of memory. It is possible to reduce memory usage by using bit strings for the sieve (one bit per boolean instead of eight bits), but the price is a significant loss of performance.
As, except for the pair (3, 5), all twins pairs are composed of a number congruent to 2 modulo 3 and a number congruent to 1 modulo 3, we can save some time by using a step of 6. Unfortunately, this is the filling of the sieve which is the most time consuming, so the gain is not very important (on our computer, half a second on a total time of 8.3 s).
<lang Nim>import math, strformat, strutils
const N = 1_000_000_000
proc sieve(n: Positive): seq[bool] =
## Build and fill a sieve of Erathosthenes.
result.setLen(n + 1) # Default to false which means prime.
result[0] = true
result[1] = true
for n in countup(3, sqrt(N.toFloat).int, 2):
if not result[n]:
for k in countup(n * n, N, 2 * n):
result[k] = true
let composite = sieve(N)
proc findTwins(composite: openArray[bool]) =
var
lim = 10
count = 1 # Start with 3, 5 which is a special case.
n = 7 # First prime congruent to 1 modulo 3.
while true:
if not composite[n] and not composite[n - 2]: inc count
inc n, 6 # Next odd number congruent to 1 modulo 3.
if n > lim:
echo &"There are {insertSep($count)} pairs of twin primes under {insertSep($lim)}."
lim *= 10
if lim > N: break
composite.findTwins()</lang>
{{out}}
<pre>There are 2 pairs of twin primes under 10.
There are 8 pairs of twin primes under 100.
There are 35 pairs of twin primes under 1_000.
There are 205 pairs of twin primes under 10_000.
There are 1_224 pairs of twin primes under 100_000.
There are 8_169 pairs of twin primes under 1_000_000.
There are 58_980 pairs of twin primes under 10_000_000.
There are 440_312 pairs of twin primes under 100_000_000.
There are 3_424_506 pairs of twin primes under 1_000_000_000.</pre>
=={{header|Perl}}==
| |||