Earliest difference between prime gaps: Difference between revisions

=={{header|Nim}}==

<syntaxhighlight lang="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

</syntaxhighlight>

{{out}}

<pre>Earliest difference > 10 between adjacent prime gap starting primes:

Gap 4 starts at 7, gap 6 starts at 23, difference is 16.

Earliest difference > 100 between adjacent prime gap starting primes:

Gap 14 starts at 113, gap 16 starts at 1831, difference is 1718.

Earliest difference > 1000 between adjacent prime gap starting primes:

Gap 14 starts at 113, gap 16 starts at 1831, difference is 1718.

Earliest difference > 10000 between adjacent prime gap starting primes:

Gap 36 starts at 9551, gap 38 starts at 30593, difference is 21042.

Earliest difference > 100000 between adjacent prime gap starting primes:

Gap 70 starts at 173359, gap 72 starts at 31397, difference is 141962.

Earliest difference > 1000000 between adjacent prime gap starting primes:

Gap 100 starts at 396733, gap 102 starts at 1444309, difference is 1047576.

Earliest difference > 10000000 between adjacent prime gap starting primes:

Gap 148 starts at 2010733, gap 150 starts at 13626257, difference is 11615524.

Earliest difference > 100000000 between adjacent prime gap starting primes:

Gap 198 starts at 46006769, gap 200 starts at 378043979, difference is 332037210.

</pre>