분류

  • 소수 알고리즘

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
def get_che(n = 2):
    che = [True] * (n + 1)
    che[0:2] = [False, False]
    
    for i in range(2, int(n ** 0.5) + 1):
        if che[i]:
            j = 2
            while i * j <= n:
                che[i * j] = False
                j += 1
    
    return che

설명

소수는 1과 자기 자신 이외에는 나눌 수 없는 수를 의미한다.

2부터 n까지 나열하고, 2부터 시작하여 배수들을 계속 지워나가는 과정을 반복한다.

약수의 성질을 이용하여 제곱근까지 확인하면 빠르게 체를 구할 수 있다.