[알고리즘] 소수 판별 : 에라토스테네스의 체

하나의 수가 소수인지 판별할 때는 간단하게 아래와 같이 짤 수 있다.

# n : 소수인지 판단할 숫자
is_prime = 1
for i in range(2, n):
	if n % i == 0:
    	is_prime = 0

 

소수를 여러번 판별할 경우 에라토스테네스의 체를 사용하는 것이 효율적이다!

10^12 의 큰 수를 소수 판별시 위의 방법 사용

10^6 이하의 모든 소수를 구할때는 에라토스테네스의 체를 활용!!

 

에라토스테네스의 체

시간 복잡도 O(nloglogn)

어떤 수가 소수가 아닌지를 판정하는 방식으로 동작

2부터 순서대로 그 수가 소수이면 그의 배수들을 모두 소수가 아님!

 

예시

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

2의 경우 소수이다.

2의 배수에 해당하는 숫자들을 소수 후보에서 삭제(4, 6, 8...)

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

그 다음 숫자는 3

3의 경우 소수이다.

3의 배수에 해당하는 숫자들을 소수 후보에서 삭제

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

 

4의 경우 소수가 아니라고 판정되었으니 다음 수로 넘어감

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

 

반복!

 

코드로 나타낼 경우

def make_prime(n):
	is_prime = [1 for _ in range(n + 1)]
    prime = []
    for i in range(2, N + 1):
    	if not is_prime[i]:
        	continue
        prime.append(i)
        
        for j in range(2 * i , n + 1, i):
        	is_prime[j] = 0
    return prime