소수 판별

import math


# 소수 판별
def is_prime_number(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x) + 1)):  # 2부터 x의 제곱근까지의 숫자
        if x % i == 0:  # 나눠떨어지는 숫자가 있으면 소수가 아님
            return False
    return True  # 전부 나눠떨어지지 않는다면 소수임

에라토스테네스의 체

임의의 자연수 n이 있으면 그 이하의 소수들을 전부 찾아내는 데 있어서 최적화된 알고리즘

def get_primes(num):
    # 에라토스테네스의 체 초기화: num개 요소에 True 설정(소수로 간주)
    # num += 1 # num까지 포함하려면
    check = [True] * num

    m = int(num ** 0.5)
    for x in range(2, m + 1):
        if check[x]:  # x가 소수인 경우
            for j in range(x + x, num, x):  # x이후의 x의 배수들은 모두 false 체크
                check[j] = False

    return [i for i in range(2, num) if check[i] == True]

소수 판별 방식으로 n이하의 소수를 구하는 것보다 에라토스테네스의 체를 이용하는게 더 빠르다.