알아두면 좋은 에라토스테네스의 체(파이썬,Python3) & 백준(S2) 4948번: 베르트랑 공준

소수: 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.

우리가 학교에서 배운 소수의 개념이다. 그래서 보통 사람들은 소수 문제를 풀 때 이 개념을 떠올리며 문제를 푼다.

그 방식이 틀린 방식은 아니지만 for 반복문을 이용해 하나씩 소수인지 아닌지 판별을 하면 시간이 오래 걸린다.

그래서 등장한 방식이 에라토스테네스의 체이다.

gif 파일을 하나 보고 가겠습니다.

숫자 2는 소수입니다. 그러므로 2의 모든 배수들은 소수가 아닙니다.

숫자 3은 소수입니다. 그러므로 3의 모든 배수들은 소수가 아닙니다.

보통 11까지 이 과정을 거치면 대부분의 숫자들은 소수인지 아닌지 알수가 있다.

그 과정을 코드와 함께 설명하겠습니다.

 

num = int(input())
prime_number_true = [False,False]+[True] * 270000
 
for i in range(2,12):
    if prime_number_true[i] == True:
        for e in range(i * 2, 270000,i):
            prime_number_true[e] = False

1부터 270000중 1개의 수를 임의로 입력 받는다고 가정하겠습니다.

prime_number_true라는 배열을 만든 뒤, 0과 1은 소수가 아니기 때문에 false값을 넣고 2부터 270000번째 수까지 True 값을 넣어줬습니다. 그 후, 2부터 11까지 반복하는 for 반복문에서 만약 prime_number_true[i]의 값이 True이면 i * 2번째부터 270000번째까지 간격을 i로 하면서 모든 배열의 값을 False로 바꿔 주었습니다.

 

 

if prime_number_true[num] == True:
    print("소수입니다.")
else:
    print("소수가 아닙니다.")
 

이후 입력 받은 값을 prime_number_true배열에 넣은 뒤, True이면 소수이고 False이면 소수가 아니라는 값을 출력하게 만들면 소수 구하는 코드는 끝이 납니다.

 

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

4948번: 베르트랑 공준

에라토스테네스의 체를 이해하고 문제를 보면 어떻게 풀어야 할지 벌써부터 감이 온다!

입력의 마지막에는 0이 주어진다만 잘 해결하면 될 것 같다.

에라토스테네스의 체를 위에서 설명했기때문에 바로 정답코드로 넘어가겠습니다.

 

정답코드:

import sys,math,time
input = sys.stdin.readline
# start = time.time()
prime_number_true = [False,False]+[True] * 270000
for i in range(2,int(math.sqrt(270000))):
    if prime_number_true[i] == True:
        for e in range(i*2,270000,i):
            prime_number_true[e] = False
 
while True:
    num = int(input())
    if num == 0:
        break
    else:
        count = 0
        for i in range(num + 1,(num * 2)+1):
            if prime_number_true[i] == True:
                count += 1
    print(count)
    # end = time.time()
    # print(f"{end - start:.5f} sec")