58 lines
1.6 KiB
Nim
58 lines
1.6 KiB
Nim
import std/[bitops, math, strformat, tables]
|
|
|
|
type Sieve = object
|
|
data: seq[byte]
|
|
|
|
proc `[]`(sieve: Sieve; idx: Positive): bool =
|
|
let idx = idx shr 1
|
|
let iByte = idx shr 3
|
|
let iBit = idx and 7
|
|
result = sieve.data[iByte].testBit(iBit)
|
|
|
|
proc `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
|
|
let idx = idx shr 1
|
|
let iByte = idx shr 3
|
|
let iBit = idx and 7
|
|
if val: sieve.data[iByte].setBit(iBit)
|
|
else: sieve.data[iByte].clearBit(iBit)
|
|
|
|
proc newSieve(lim: Positive): Sieve =
|
|
result.data = newSeq[byte]((lim + 16) shr 4)
|
|
|
|
proc initPrimes(lim: Positive): seq[Natural] =
|
|
var composite = newSieve(lim)
|
|
composite[1] = true
|
|
for n in countup(3, sqrt(lim.toFloat).int, 2):
|
|
if not composite[n]:
|
|
for k in countup(n * n, lim, 2 * n):
|
|
composite[k] = true
|
|
for n in countup(3, lim, 2):
|
|
if not composite[n]:
|
|
result.add n
|
|
|
|
const Limit = 100_000_000
|
|
let primes = initPrimes(Limit * 5)
|
|
var gapStarts: Table[int, int]
|
|
for i in 1..primes.high:
|
|
let gap = primes[i] - primes[i - 1]
|
|
if gap notin gapStarts:
|
|
gapStarts[gap] = primes[i - 1]
|
|
var pm = 10
|
|
var gap1 = 2
|
|
while true:
|
|
while gap1 notin gapStarts:
|
|
inc gap1, 2
|
|
let start1 = gapStarts[gap1]
|
|
let gap2 = gap1 + 2
|
|
if gap2 notin gapStarts:
|
|
gap1 = gap2 + 2
|
|
continue
|
|
let start2 = gapStarts[gap2]
|
|
let diff = abs(start2 - start1)
|
|
if diff > pm:
|
|
echo &"Earliest difference > {pm} between adjacent prime gap starting primes:"
|
|
echo &"Gap {gap1} starts at {start1}, gap {gap2} starts at {start2}, difference is {diff}.\n"
|
|
if pm == Limit: break
|
|
pm *= 10
|
|
else:
|
|
gap1 = gap2
|