Python/maths/segmented_sieve.py at master · BAW2501/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""Segmented Sieve."""

importmath


defsieve(n: int) ->list[int]:
"""Segmented Sieve."""
in_prime= []
start=2
end=int(math.sqrt(n)) # Size of every segment
temp= [True] * (end+1)
prime= []

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

low=end+1
high=min(2*end, n)

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

forjinrange(t, high+1, each):
temp[j-low] =False

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

low=high+1
high=min(high+end, n)

returnprime


print(sieve(10**6))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""Segmented Sieve."""

importmath


defsieve(n: int) ->list[int]:
"""Segmented Sieve."""
in_prime= []
start=2
end=int(math.sqrt(n)) # Size of every segment
temp= [True] * (end+1)
prime= []

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

low=end+1
high=min(2*end, n)

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

forjinrange(t, high+1, each):
temp[j-low] =False

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

low=high+1
high=min(high+end, n)

returnprime


print(sieve(10**6))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""Segmented Sieve."""

importmath


defsieve(n: int) ->list[int]:
"""Segmented Sieve."""
in_prime= []
start=2
end=int(math.sqrt(n)) # Size of every segment
temp= [True] * (end+1)
prime= []

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

low=end+1
high=min(2*end, n)

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

forjinrange(t, high+1, each):
temp[j-low] =False

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

low=high+1
high=min(high+end, n)

returnprime


print(sieve(10**6))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""Segmented Sieve."""

importmath


defsieve(n: int) ->list[int]:
"""Segmented Sieve."""
in_prime= []
start=2
end=int(math.sqrt(n)) # Size of every segment
temp= [True] * (end+1)
prime= []

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

low=end+1
high=min(2*end, n)

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

forjinrange(t, high+1, each):
temp[j-low] =False

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

low=high+1
high=min(high+end, n)

returnprime


print(sieve(10**6))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""Segmented Sieve."""

importmath


defsieve(n: int) ->list[int]:
"""Segmented Sieve."""
in_prime= []
start=2
end=int(math.sqrt(n)) # Size of every segment
temp= [True] * (end+1)
prime= []

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

low=end+1
high=min(2*end, n)

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

forjinrange(t, high+1, each):
temp[j-low] =False

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

low=high+1
high=min(high+end, n)

returnprime


print(sieve(10**6))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""Segmented Sieve."""

importmath


defsieve(n: int) ->list[int]:
"""Segmented Sieve."""
in_prime= []
start=2
end=int(math.sqrt(n)) # Size of every segment
temp= [True] * (end+1)
prime= []

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

low=end+1
high=min(2*end, n)

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

forjinrange(t, high+1, each):
temp[j-low] =False

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

low=high+1
high=min(high+end, n)

returnprime


print(sieve(10**6))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""Segmented Sieve."""

importmath


defsieve(n: int) ->list[int]:
"""Segmented Sieve."""
in_prime= []
start=2
end=int(math.sqrt(n)) # Size of every segment
temp= [True] * (end+1)
prime= []

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

low=end+1
high=min(2*end, n)

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

forjinrange(t, high+1, each):
temp[j-low] =False

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

low=high+1
high=min(high+end, n)

returnprime


print(sieve(10**6))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""Segmented Sieve."""

importmath


defsieve(n: int) ->list[int]:
"""Segmented Sieve."""
in_prime= []
start=2
end=int(math.sqrt(n)) # Size of every segment
temp= [True] * (end+1)
prime= []

whilestart<=end:
iftemp[start] isTrue:
in_prime.append(start)
foriinrange(start*start, end+1, start):
temp[i] =False
start+=1
prime+=in_prime

low=end+1
high=min(2*end, n)

whilelow<=n:
temp= [True] * (high-low+1)
foreachinin_prime:
t=math.floor(low/each) *each
ift<low:
t+=each

forjinrange(t, high+1, each):
temp[j-low] =False

forjinrange(len(temp)):
iftemp[j] isTrue:
prime.append(j+low)

low=high+1
high=min(high+end, n)

returnprime


print(sieve(10**6))