-
Notifications
You must be signed in to change notification settings - Fork 1
/
prime.py
40 lines (31 loc) · 862 Bytes
/
prime.py
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
from math import sqrt
def prime(n: int) -> int:
# n is required to be grater than 2
if n == 2:
return 2
elif n < 2:
return 0
# length of sieve array (ignore even number)
N = int((n-1)/2)
# max value to check division
sqrtn = int(sqrt(n))
# sieve array correspond to [3, 5, 7, 9, ..., ]
arr = [True] * N
for i in range(N):
x = 2*(i+1) + 1
# theoretically, no need to check the value grater than sqrt(n)
if x > sqrtn:
break
for j in range(i+1, N):
if not arr[j]:
continue
y = 2*(j+1) + 1
if y % x == 0:
arr[j] = False
# check max prime below n
max_val = 2
for i in reversed(range(N)):
if arr[i]:
max_val = 2*(i+1) + 1
break
return max_val