BOJ 4948번 : 베르트랑 공준

안녕하세요. 지난 포스팅의 BOJ 1929번 : 소수 구하기에서는 정수론 지식을 활용해서 보다 빠르게 소수 판별을 할 수 있는 방법에 대해서 알아보았습니다. 오늘은 이보다 더욱 빠르게 소수의 개수를 계산해야하는 문제를 풀기 위해 에라토스테네스의 체에 대한 개념을 알아보고 적용해보도록 하겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 기본 구현능력
• 에라토스테네스의 체

 

제출 코드

while True :
    N = int(input())
    if N == 0 : break
    prime = [1 for i in range(2*N+1)]
    prime[0] = prime[1] = 0
    for number, _ in enumerate(prime) :
        if prime[number] ==  1 :
          for j in range(2*number, 2*N+1, number) :
              prime[j] = 0
        else : continue
    print(sum(prime[N + 1 : 2*N + 1]))

 

해설

문제의 입력은 0이 들어올 때 까지 계속 입력을 받아야하기 때문에 while 구문을 활용하고 만약 0이면 break 구문을 이용해서 반복문을 탈출하는 것으로 정했습니다. 

 

 

에라토스테네스의 체란 간단한 소수판별 알고리즘이지만 강력합니다. 일단, 저희는 기본적으로 소수가 아닌 수는  소수의 배수가 될 수 있음을 상기해야합니다. 예를 들어, 68의 경우에는 2의 배수, 65의 경우에는 5의 배수가 되기 때문에 소수가 아니죠. 하지만, 2와 5는 소수입니다. 이와 같이 배수의 기본이 되는 수를 제외하는 체로 걸러가는 과정을 에라토스테네스의 체라고 하죠.

 

이를 실제 코딩을 구현해보도록 하겠습니다. 일단, 모든 수가 소수라고 가정하고 시작하기 위해 prime 변수에 $N + 1$ 만큼의 수를 할당해줍니다. 이때, 각 인덱스의 숫자가 소수면 1, 아니면 0으로 표기하도록 하겠습니다. 이때, 기본적으로 0과 1은 소수가 아니기 때문에 해당 인덱스의 값을 1에서 0으로 바꾸어줍니다 (prime[0] = prime[1] = 0). 다음으로 할 일은 각 인덱스를 확인하면서 소수가 아니라면 다음 인덱스를 확인하고 소수라면 에라토스테네스의 체를 적용해주면 됩니다. 즉, 소수라고 판명이 난 수에 대한 배수들을 정해진 범위만큼의 모든 인덱스들의 값을 0으로 바꾸어줍니다. 저희는 이를 range 함수로 쉽게 구현할 수 있습니다. 일단, number는 이미 소수라고 판명이 난 상태이기 때문에 number의 다음 배수인 2 * number부터 시작해서 입력된 범위까지 조사를 하게 됩니다. range 함수의 세번째 인자는 해당 인자만큼 더해서 새로운 리스트를 만들어주기 때문에 number를 넣는다면 3 * number, 4 * number, ...와 같은 number 배수들의 리스트를 얻을 수 있습니다. 이제 각 배수들의 값을 전부 0으로 치환해주면 되죠. 

 

마지막으로 주어진 범위인 $N + 1 ~ 2N$ 내에서 소수의 개수를 판별하기 위해서 prime[N + 1 : 2*N + 1]에 sum 함수를 통해 소수로 판별된 인덱스들의 개수를 계산할 수 있습니다. 

 

참고자료 및 그림출처

백준 코딩 문제