Twin primes: Difference between revisions
Content added Content deleted
Catskill549 (talk | contribs) |
|||
Line 731: | Line 731: | ||
return true |
return true |
||
}</lang> |
}</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}}== |
=={{header|Perl}}== |