[Python - Math] 1978 소수 찾기(에라토스테네스의 체)

📌 문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

📌 입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

📌 출력

주어진 수들 중 소수의 개수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

에라토스테네스의 체를 사용하여 소수를 쉽게 찾아낼 수 있다.

소수를 찾는 방법에는 여러 가지 방법이 있다.

가장 쉬운 방법은 for문으로 2부터 n까지 탐색해보는 방법이다.

def is_prime_number(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

이 경우 n까지 모두 탐색하는 방법으로 시간복잡도는 O(N)이라고 할 수 있다.

---

그런데 소수 판별의 특성상 처음부터 끝까지 모두 탐색할 필요는 없다.

 

예를 들어, 16의 약수는 1, 2, 4, 8, 16인데 잘 보면 양 끝부터 시작해서 16을 만들어낼 수 있다. 1 * 16 = 16, 2 * 8 = 16, 4 * 4 = 16이다. 이걸 보면 16의 약수에서 중간까지만 탐색해도 되지 않을까? 하는 생각이 들 것이다. 동일한 상황에서 4를 넘어가서 8로 16을 구하는 것은 8 * 2를 하는 것인데 이것은 2 * 8과 다를 바 없기 때문이다. 즉, 우리는 N의 제곱근까지만 탐색해도 된다는 것이다.

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

이 경우는 제곱근까지 탐색하는 것이라서 시간복잡도는 O(√N)이다.

---

또 다른 방법은 에라토스테네스의 체를 사용하는 것이다. 만약 다수의 소수를 찾아야 하는 상황에서는 대략적으로 위의 시간복잡도에서 각각 X를 곱한 만큼의 시간이 소요될 것이다. 이렇게 다수의 소수를 찾을 때 O(NloglogN)의 시간복잡도로 소수를 구할 수 있는 방법이 바로 에라토스테네스의 체이다.

 

간결하게 말하자면, 2부터 N까지 소수를 탐색하다가 소수를 찾으면, 그 소수의 모든 배수는 소수가 아니기 때문에 미리 체크해두는 것이다.

 

2는 소수이기 때문에 2의 배수인 4, 6, 8, 10, ...은 모두 제외한다. 그 이후 3도 소수이기 때문에 6, 9, 12, 15, ...은 모두 제외한다. 5도 같은 방법으로 제외하고, N까지 제외하면 소수만 남는 소수 테이블이 만들어진다.

이제 이 테이블에서 인덱스를 통해서 소수인지 아닌지만 꺼내서 쓰면 되는 것이다.

def sieve_of_eratosthenes(n):
    sieve = [False, False] + [True] * (n - 1)
    for i in range(2, n + 1):
        if not sieve[i]:
            for k in range(i * 2, n + 1, i):
                sieve[k] = False
    return sieve

prime_numbers = eratosthenes(10)

for i in range(2, 10)
    if prime_numbers[i]:
        print(i)

👨‍🏫 문제 풀이

📄 전체 코드

from sys import stdin


def eratosthenes(n):
    prime_numbers = [False, False] + [True] * (n - 1)

    for i in range(2, n + 1):
        if prime_numbers[i]:
            for k in range(i * 2, n + 1, i):
                prime_numbers[k] = False

    return prime_numbers


n = int(stdin.readline())

l = eratosthenes(1001)
ans = 0

k = list(map(int, stdin.readline().split()))

for i in k:
    if l[i]:
        ans += 1

print(ans)

📄 준비

from sys import stdin
n = int(stdin.readline())

l = eratosthenes(1001)
ans = 0

k = list(map(int, stdin.readline().split()))

for i in k:
    if l[i]:
        ans += 1

print(ans)

📄 풀이

def eratosthenes(n):
    prime_numbers = [False, False] + [True] * (n - 1)

    for i in range(2, n + 1):
        if prime_numbers[i]:
            for k in range(i * 2, n + 1, i):
                prime_numbers[k] = False

    return prime_numbers

📌 총평

알고리즘 전체 코드를 안 보고 이렇게 알고리즘을 작성하면 되지 않을까? 하고 에라토스테네스의 체를 구현했는데 바로 성공했다. WOW