시간 복잡도 : 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()