[435] 에라토스테네스의 체(소수 구하기) (파이썬 코드)

1. 에라토스테네스의 체(소수 구하기) (파이썬 코드)

n = 50
p = [True] * (n+1)
p[0], p[1] = False, False
for i in range(2, int(n**0.5)+1):
    if p[i]:
        for j in range(i*2, n+1, i):
            p[j] = False
print([i for i in range(n+1) if p[i]])
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

풀어볼 문제: 소수 구하기(https://www.acmicpc.net/problem/1929)

2. 소수(Prime Number)

1 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말합니다.

3. 소수 판별하기

1 보다 큰 자연수 n이 주어졌을 때, n이 소수인지 판별하는 방법을 알아봅시다.

먼저, 소수의 정의를 이용해서 n을 2 부터 (n-1) 까지 나누어 본 후, 나누어지는 수가 없다면 n은 소수입니다.

cnt = 0
def is_prime(n):
    global cnt
    for i in range(2, n):
        cnt += 1
        if n%i == 0:
            return False
    return True

print(is_prime(100000007))
# True
print(cnt)
# 100000005

코드로 구현하여 확인해보면 100000007(1억 7)은 조금 시간이 걸리지만 확인이 됩니다.

하지만 (n-2)만큼 반복하므로 O(n) 시간이 걸립니다.

 

조금만 생각해보면 굳이 n-1까지 나누어 볼 필요가 없다는 것을 알 수 있습니다.

왜냐하면 n이 소수가 아니라면 1과 n이 아닌 두 수의 곱으로 나타낼 수 있습니다.

그리고 이 두 수 중에 더 작은 수는 \(\sqrt{n}\)보다 같거나 작을 것이기 때문에 \(\sqrt{n}\)까지만 나누어 보면 됩니다.

cnt = 0
def is_prime(n):
    global cnt
    for i in range(2, int(n**0.5)+1):
        cnt += 1
        if n%i == 0:
            return False
    return True

print(is_prime(100000007))
# True
print(cnt)
# 9999

4. n까지의 모든 소수 구하기

이제 소수 판별하는 방법을 배웠으니 n까지의 모든 소수를 구해봅시다.

앞서 만든 소수 판별 함수를 사용하여 1000000(백만)까지의 소수를 구해보겠습니다.

cnt = 0
def is_prime(n):
    global cnt
    for i in range(2, int(n**0.5)+1):
        cnt += 1
        if n%i == 0:
            return False
    return True

print([i for i in range(2, 1000001) if is_prime(i)])
# [2, 3, 5, 7, ... 999959, 999961, 999979, 999983]

print(cnt)
# 67740404

100만 까지의 모든 소수를 찾는데 총 67,740,404번 반복합니다.

 

이제 에라토스테네스의 체를 활용해봅시다.

에라토스테네스의 체는 다음과 같은 과정을 거칩니다.

먼저, 소수는 1 보다 큰 자연수 범위이므로, 1은 소수가 아닙니다.

다음으로 2는 소수이고, 2의 배수는 모두 2로 나누어지므로 소수가 아닙니다.

확인하지 않은 다음 수는 3이고, 3은 이전에 나누어떨어진 수가 없으므로 소수입니다.

마찬가지로 3의 배수는 소수가 아닌 것이 확인됩니다.

확인하지 않은 다음 수인 5는 소수이고, 5의 배수는 소수가 아닙니다.

그 다음 확인하지 않은 수인 7은 소수가 되고, 7의 배수는 소수가 아닙니다.

 

이렇게 n까지 반복하면 모든 소수를 구할 수가 있습니다.

하지만 소수 판별과 마찬가지고 굳이 n까지 반복할 필요가 없습니다.
\(\sqrt{n}\)까지 반복하면서 그보다 작은 소수들의 배수가 모두 지워졌으므로, 남은 수는 모두 약수가 자신과 1 뿐입니다.

따라서 \(\sqrt{n}\)까지 반복하고 남은 모든 수는 소수입니다.

위 과정을 코드로 구현하면 다음과 같습니다.

100만까지의 소수를 확인해봅시다.

n = 1000000
p = [True] * (n+1)
p[0], p[1] = False, False # 0과 1은 소수가 아님.
cnt = 0
for i in range(2, int(n**0.5)+1): # 2부터 루트n까지 반복
    cnt += 1
    if p[i]: # i가 소수이면,
        for j in range(i*2, n+1, i): # i의 배수는 모두 소수가 아님.
            cnt += 1
            p[j] = False
            
print([i for i in range(n+1) if p[i]])
# [2, 3, 5, 7, ... 999959, 999961, 999979, 999983]

print(cnt)
# 2198838

에라토스테네스의 체를 활용하여 100만까지 모든 소수를 확인해 본 결과, 2,198,838번 반복됩니다.

앞서 일일이 소수인지 확인하는 코드보다 훨씬 효율적입니다.