시간 복잡도 : O(N**0.5)
import math
# 소수 판별 함수
def is_prime_number(x):
if x < 2:
return False # 2 이하 소수 아님
# 2부터 x의 제곱근까지의 모든 수를 확인하며
for i in range(2, int(math.sqrt(x)) + 1):
# x가 해당 수로 나누어떨어진다면
if x % i == 0:
return False # 소수가 아님
return True # 소수임
print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임
# 소수면 1 아니면 0, N 값까지의 소수 찾기.
def is_prime_list(N = 1000001):
prime = []
check = [1] * N
check[0] = 0
check[1] = 0
for i in range(2, N):
if check[i] == 1:
prime.append(i)
for j in range(2*i, N, i):
check[j] = 0
return prime, check
prime, check = is_prime_list()