[백준 4948번 파이썬] 에라토스테네스의 체를 사용한 문제 풀이

 

https://www.acmicpc.net/problem/4948

 

 

이 풀이를 찾으려고 들어왔다면 여러분들의 코드는 아마

import sys
import math

def is_prime(number):
    if number <= 1:
        return False
    if number <= 3:
        return True
    if number % 2 == 0 or number % 3 == 0:
        return False
    i = 5
    while i * i <= number:
        if number % i == 0 or number % (i + 2) == 0:
            return False
        i += 6
    return True

def count_primes_in_range(n):
    count = 0
    for num in range(n + 1, 2 * n + 1):
        if is_prime(num):
            count += 1
    return count

def main():
    input = sys.stdin.read
    data = list(map(int, input().split()))

    for n in data:
        if n == 0:
            break
        print(count_primes_in_range(n))

if __name__ == "__main__":
    main()

이런식으로 작성 되어있을 가능성이 크다고 생각합니다.

 

우리는 에라토스테네스의 체를 사용해서 문제 풀이를 해야합니다.

 

에라토스테네스의 체란?

소수를 효율적으로 구하는 방법 중 하나로 유명한 에라토스테네스의 체 알고리즘입니다.이 알고리즘을 파이썬 코드로 구현하고, 어떻게 동작하는지 단계별로 설명하겠습니다.

 

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 만든 소수 판별 방법입니다. 이 방법은 주어진 범위 내의 모든 소수를 빠르고 효율적으로 구할 수 있습니다. 핵심 아이디어는 2부터 시작하여 그 수의 배수를 모두 제거해 나갑니다. 결국 남은 숫자들은 소수가 됩니다.

 

import sys
input = sys.stdin.readline

def prime_numbers(n):
    arr = [i for i in range(n+1)]
    end = int(n ** (1/2))
    for i in range(2, end+1):
        if arr[i] == 0:
            continue
        for j in range(i*i, n+1, i):
            arr[j] = 0
    return [i for i in arr[2:] if arr[i]]

 

 

이 코드를 단계별로 설명해보겠습니다.

 

arr = [i for i in range(n+1)]

 

여기서는 0부터 n까지의 모든 숫자를 포함하는 리스트 arr를 생성합니다. 이 리스트는 소수 여부를 판별하는 데 사용됩니다. 초기에는 각 숫자에 해당하는 인덱스에 그 숫자 자체를 할당합니다.

 

end = int(n ** (1/2))

 

 

에라토스테네스의 체 알고리즘은 n의 제곱근까지만 반복해도 충분합니다. 이유는 그 이상의 숫자에서 발생하는 배수들은 이미 앞선 과정에서 처리되었기 때문입니다. 따라서 여기서는 제곱근을 계산해 반복 범위를 줄입니다.

 

 

for i in range(2, end+1):
    if arr[i] == 0:
        continue
    for j in range(i*i, n+1, i):
        arr[j] = 0

 

 

 

• 이 부분에서 i를 2부터 시작하여, 현재 숫자가 소수인지 확인합니다.
• 만약 arr[i]가 0이라면 이미 이전에 처리된 숫자이므로 건너뜁니다.
• i가 소수라면, 그 배수들을 모두 0으로 설정하여 소수가 아님을 표시합니다. 이때 i*i부터 시작하는 이유는 그 이전의 배수들은 이미 처리되었기 때문입니다.

 

return [i for i in arr[2:] if arr[i]]

 

 

 

마지막으로, 리스트에서 0이 아닌 값만 추출하여 소수 목록을 반환합니다. 여기서 arr[2:]는 2부터 시작하는 모든 숫자를 의미합니다. 따라서 소수로 남아 있는 숫자들만 리스트로 반환됩니다.

최종 출력

이 코드가 반환하는 것은 주어진 범위 내의 소수 목록입니다. 예를 들어, prime_numbers(10)을 호출하면 [2, 3, 5, 7]이라는 결과를 얻게 됩니다.

 

 

while 1:
    x = int(input().strip())
    if x == 0:
        break
    print(len(prime_numbers(2 * x)) - len(prime_numbers(x)))

 

 

이 코드를 아래부분에 붙여주면 끝입니다. 

도움되셨다면 공감버튼 눌러주시면 감사하겠습니다.