분류


  • 소수 알고리즘

알고리즘 코드


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부터 시작하여 배수들을 계속 지워나가는 과정을 반복한다.

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