iframe-proxy | Sunbelt Computer Software

History

51 lines (38 loc) · 1.09 KB

Raw

"""Segmented Sieve."""

import math

def sieve(n):

"""Segmented Sieve."""

in_prime = []

start = 2

end = int(math.sqrt(n)) # Size of every segment

temp = [True] * (end + 1)

prime = []

while start <= end:

if temp[start] is True:

in_prime.append(start)

for i in range(start * start, end + 1, start):

if temp[i] is True:

temp[i] = False

start += 1

prime += in_prime

low = end + 1

high = low + end - 1

if high > n:

high = n

while low <= n:

temp = [True] * (high - low + 1)

for each in in_prime:

t = math.floor(low / each) * each

if t < low:

t += each

for j in range(t, high + 1, each):

temp[j - low] = False

for j in range(len(temp)):

if temp[j] is True:

prime.append(j + low)

low = high + 1

high = low + end - 1

if high > n:

high = n

return prime

print(sieve(10 ** 6))

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

segmented_sieve.py

Latest commit

History

segmented_sieve.py

File metadata and controls