백준 4948번 - 베르트랑 공준 (Feat. 에라토스테네스의 체)

이 문제는 입력값이 1~123,456 이므로 이중 for문을 이용하는 일반적인 소수 판별법으로는 시간 초과가 나올 것이 분명했다. 문제의 설명란에 에라토스테네스의 체로 풀어보자는 말이 있으므로 구글링을 해봤다.

출처:위키백과

위의 사진은 120까지의 자연수 중에서 소수를 모두 구하는 과정을 보여준다. 과정은 간단하다. 

2의 배수를 모두 지우고, 그 다음엔 3의 배수를 지운다. 4는 이미 앞에서 2의 배수를 지울 때 지워졌기 때문에 4가 아닌 5로 넘어가서 5의 배수를 모두 지운다. 여기서 포인트는 위의 예에서 120까지의 소수를 구하는 것이 목적인데, 

120 < 11^2 이므로 11까지만 이 과정을 반복해주면 된다. 이 과정을 반복하면 소수만 남는다는 것이 에라스토테네스의 체이다.

프로그래밍 언어로 구현하기는 생각보다 어렵지 않다. 

N개의 True 값을 가진 배열을 만들어서 for문을 이용해서 N의 제곱근만큼 반복을 해주면서 배수들을 지워주기만 하면 된다. 

##변수 선언 부분
isPrime = 0
cnt = 0
prime = []
##메인 함수 부분
if __name__ == "__main__":
    prime = 250000 * [True] #250000개의 True가 들어있는 배열을 만들어준다.
    for i in range(2,500): #250000의 제곱근만큼 반복해줘도 된다
        for j in range(2*i,250000,i): #본인의 배수들을 모두 지워준다.
            if prime[j]:
                prime[j] = False

    while True:
        cnt = 0
        T = int(input())
        if T == 0: #0이 입력되면 종료
            break
        for i in range(T+1,T*2+1): #본인 + 1 ~ 본인 * 2까지
            if prime[i] == True: #소수면 cnt 증가
                cnt += 1

        print(cnt)

 

이 문제에서는 25만개의 배열을 만들어서 소수가 되는 인덱스에만 True가 남게 했다. 문제를 풀기 전에 최대의 가능한 소수를 모두 구해준 뒤 문제를 푼 것이다. 실행 시간에 있어서 효율적인 알고리즘이므로 소수 문제를 풀 때는 웬만하면 이 알고리즘을 사용하자