파이썬 N까지의 소수 개수 구하기

파이썬에서 1 ~ N까지의 소수 개수를 구할때는 아래와 같이 작성할 수 있다.

n = int(input())

result = []

for i in range(2, n + 1):

    temp = []

    for j in range(1, i + 1):

        if i % j == 0:

            temp.append(j)

    if len(temp) == 2:

        result.append(i)

print(len(result))

하지만 위 코드는 각 숫자마다 모든 약수를 구하고, 그 약수의 개수를 확인하는 부분이 시간 복잡도를 크게 증가시킨다.

 

해당 문제를 해결하기 위해서는 에라토스테네스의 체를 이용하면 된다. 에라토스테네스의 체는 임의의 수 n 에 대해서 그 이하의 소수를 모두 찾는 간단하면서 빠른 방법이다.

먼저 임의의 수를 100이라고 하면 

1. 1 ~ 100 까지의 숫자를 적는다.

2. 소수, 합성수가 아닌 자연수를 제거한다.

3. 2를 제외한 2의 배수를 제거한다.

4. 3을 제외한 3의 배수를 제거한다.

5. 4의 배수는 이미 2의 배수에서 지워졌기 때문에 넘어간다.

6. 2, 3 다음으로 남아있는 소수인 5, 5를 제외한 5의 배수를 제거한다.

7. 7을 제외한 7의 배수를 제거한다.

 

알고리즘을 요약하자면

1. 2부터 시작하여 배수를 지워나간다.

2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾아 그 수의 배수를 모두 지운다.

3. 위의 과정을 반복한다.

 

def count_primes(n):

    is_prime = [True] * (n + 1)

    is_prime[0] = is_prime[1] = False  

    for i in range(2, int(n**0.5) + 1):

        if is_prime[i]:

            for j in range(i * i, n + 1, i):

                is_prime[j] = False

    primes = [num for num in range(2, n + 1) if is_prime[num]]

    return len(primes)

n = int(input())

result = count_primes(n)

print(result)

위의 알고리즘을 토대로 코드를 작성할 수 있다. [0] [1]이 False인 이유는 0과 1이 입력되었을때의 예외 처리이다.

0과 1은 소수가 아니기 때문이다.