[Algorithm] Prime Number / Sieve of Eratosthenes

Prime Number (소수)

• 약수가 1 과 자기 자신밖에 없는 1보다 큰 양수

양수 N 이 소수인지 확인하는 방법은 아래의 코드와 같이
일일이 확인하는 방법이 있다.

def is_prime(num):
    if num <= 1: return False
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

print(is_prime(2))
print(is_prime(6))
print(is_prime(101))

>>> True
>>> False
>>> True

Sieve of Eratosthenes

• 에라토스테네스의 체

1	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

위와 같이 수를 나열하였을 때 모든 수를 소수라고 가정한다. (1은 제외)

이제 2 부터 순서대로
2 자신을 제외한 모든 2의 배수를 소수 목록에서 제거한다.

1	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

2 의 배수를 모두 제거함에따라
제거되지 않은 수 중 가장 작은 값은 3 이다.
3 자신을 제외한 3 의 배수를 모두 제거한다.

1	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

2 와 3 의 배수를 제거함에따라
제거되지 않은 수 중 가장 작은 값은 5 이다.
5 자신을 제외한 5 의 배수를 모두 제거한다.

1	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

2, 3, 그리고 5 의 배수를 제거함에따라
제거되지 않은 수 중 가장 작은 값은 7 이다.
7 자신을 제외한 7 의 배수를 모두 제거한다.

1	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

2, 3, 5, 7 의 배수를 제거함에따라
제거되지 않은 수 중 가장 작은 값은 11 이다.
11 자신을 제외한 11 의 배수를 모두 제거한다.
이 때 11 자신을 제외한 11 의 배수는 이미 제거되어 있으므로 패스한다.

2, 3, 5, 7, 11 의 배수를 제거함에따라
제거되지 않은 수 중 가장 작은 값은 13 이다.
13 자신을 제외한 13 의 배수를 모두 제거한다.
이 때 13 자신을 제외한 13 의 배수는 이미 제거되어 있으므로 패스한다.

위와 같은 과정을 나열된 수의 가장 큰 값인 50 까지 반복하여
최종적으로 남아있는 수가 소수가 된다.

Result

1	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

제거되지않고 남은 수

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

가 소수가 된다.

에라토스테네스의 체를 Python 코드로 구현할 경우 아래와 같다.

Python Implementation Code

def eratosthenes(n):
    e = [True for _ in range(n+1)]
    e[0], e[1] = False, False
    primes = list()
    for i in range(2, n+1):
        if e[i]:
            primes.append(i)
            for j in range(i*2, n+1, i):
                e[j] = False
    return primes

print(eratosthenes(50))

>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]