46 lines
942 B
Nim
46 lines
942 B
Nim
|
import math, sequtils
|
||
|
|
proc simple(limit: int): seq[int] =
|
||
|
|
var isPrime = newSeq[bool](limit + 1)
|
||
|
|
for i in 0..limit:
|
||
|
|
isPrime[i] = true
|
||
|
|
isPrime[0] = false
|
||
|
|
isPrime[1] = false
|
||
|
|
|
||
|
|
for i in 2..int(sqrt(float(limit))):
|
||
|
|
if isPrime[i]:
|
||
|
|
var j = i * i
|
||
|
|
while j <= limit:
|
||
|
|
isPrime[j] = false
|
||
|
|
j += i
|
||
|
|
|
||
|
|
result = @[]
|
||
|
|
for i, prime in isPrime:
|
||
|
|
if prime:
|
||
|
|
result.add(i)
|
||
|
|
|
||
|
|
proc segmented(L, R: int): seq[int] =
|
||
|
|
let limit = int(sqrt(float(R)))
|
||
|
|
let primes = simple(limit)
|
||
|
|
var isPrime = newSeq[bool](R - L + 1)
|
||
|
|
for i in 0..<isPrime.len:
|
||
|
|
isPrime[i] = true
|
||
|
|
|
||
|
|
for p in primes:
|
||
|
|
var start = (L div p) * p
|
||
|
|
if start < L: start += p
|
||
|
|
if start == p: start += p
|
||
|
|
|
||
|
|
var j = start
|
||
|
|
while j <= R:
|
||
|
|
isPrime[j - L] = false
|
||
|
|
j += p
|
||
|
|
|
||
|
|
result = @[]
|
||
|
|
for i in 0..<isPrime.len:
|
||
|
|
if isPrime[i] and (i + L >= 2):
|
||
|
|
result.add(i + L)
|
||
|
|
|
||
|
|
let L = 10
|
||
|
|
let R = 500000000
|
||
|
|
echo segmented(L, R)
|