10001번째의 소수

사이트 이름 - 문제 7번

• 10001번째의 소수

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요.

해결방법

이건 일전에 소수 구하는 함수를 이용해서 풀면 되겠다.

하도 느려서 소수 구하는 알고리즘을 다시 만들었다.

def is_prime(number):
    if number < 2:
        return False

    if number == 2:
        return True
    
    if number % 2 == 0:
        return False

    for i in range(3, int(number ** 0.5) + 1):
        if number % i == 0:
            return False

    return True


i = 2
cnt = 0  # 10001 번째 소수를 찾기위해 카운트
while True:
    if is_prime(i):
        cnt += 1
        if cnt == 10001:
            break
    i += 1

print(i) # 104743

에라토스테네스의 체(The sieve of Eratosthenes)

이 문제를 풀기위해 프로젝트 오일러에서 제공하는 해법

주어진 자연수 n까지의 모든 소수를 찾는 고대의 알고리즘이다. 첫 소수인 2부터 시작해서 각 소수의 배수가 되는 합성수를 제거하는 방법을 반복하여 모든 소수를 걸러낸다. 작은 범위에서 모든 소수를 찾아내는 가장 효율적인 방법 중 하나이다.

알고리즘

1. 2부터 까지의 모든 자연수의 목록을 만든다: (2, 3, 4, ..., n).
2. 초기 상태에 변수  값으로 최소 소수인 2를 대입한다.
3. 2p에서 까지 모든 의 배수를 목록에서 찾아 제거 표시한다: (2p, 3p, 4p, ...; p는 제외).
4. p보다 큰 수 중에서 제거 표시가 안 된 가장 작은 수를 찾는다. 그런 수가 없다면 종료하고, 있다면 그 수를 에 대입하고 3번부터 다시 반복한다.
5. 알고리즘이 종료할 때, 목록에서 제거 표시가 되지 않고 남아 있는 수들이 까지의 모든 소수이다.

에라토스테네스의 체는 소수의 개수를 세는 데도 사용될 수 있다.