<수학2> 1929번 소수 구하기 with 파이썬

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

정답비율

27.379%

 

 

 이 문제를 보고 앞의 문제와 똑같이 소수를 구하면 될것이라고 생각하였다. 물론 정답비율과 더 넓어진 범위, 그리고 짧은 제한시간이 마음에 걸렸다. 어쨋든 기존과 같은 방식으로 숫자 하나하나를 2부터 그 숫자까지 나눠가며 약수가 있는지 체크하였다. 당연히 시간초과로 오답이 되었다.

 

 그래서 생각한 두 번째 방식은 이렇다. 제곱근까지만 체크하여 시간을 반으로 줄여보자. 예를 들면 이렇다. 10이 소수인지 체크한다고 가정하자. 그러면 10은 1*10 , 2*5, 5*2, 10*1 로 나타나는데 이 때 우리는 굳이 5와 10에 대해서는 체크할 필요가 없다. 쉽게 말해 10의 제곱근(약수의 중간)인 3.xxxx 까지만 체크해서 약수가 1뿐이라면 반드시 소수인 것이다. 즉 제곱근 이상의 숫자에 대해서는 체크할 필요는 없다. 이를 코딩하면 다음과 같았다.

M, N = map(int,input().split())
for i in range(M,N+1) :
    if i == 1 :
        continue
    elif i == 2 :
        print(i)
    else :
        for j in range(2, int(i**1/2)+1) :
            if i%j == 0 :
                break
            elif j == int(i**1/2) :
                print(i)

 시간을 절반으로 줄일 수 있음에도 시간초과가 나왔다. 다른사람들이 푼 것을 보니 대부분 제곱근을 이용해서 풀었던데, 아무래도 시간제한에 업데이트가 있어 보였다. 더 검색해보니 에라토스테네스의 체를 이용해서 풀어야한다고 한다. 어쩔 수 없이 에라토스테네스의 체를 공부하였다.

 

 에라토스테네스의 체는 대량의 소수를 구할 때 쓰이는 방법이다. 1에서 10까지 숫자 중에서 소수를 찾는다고 가정해보자. 1은 당연히 제외시키고 2부터 시작한다. 2는 소수이고, 그럼 2의 배수들은 모두 거른다. 그 다음 3을 보자. 3은 소수이다. 그럼 3의 배수들은 거른다. 그 다음은 4이지만 이미 걸러졌으므로 5로 넘어간다. 이러한 방식을 반복하면 자연스럽게 2 3 5 7 만 남게된다. 

 

 나는 이를 구현하기 위해서 거른다는 표현을 True 에서 False로 바꾸는 방식을 선택했다. 왜냐하면 리스트에서 숫자들을 빼버리면 인덱스를 활용하기 까다로워 질 것 같아서이다.

M, N = map(int, input().split())
x = [False, False]+[True]*(N-1)
for i in range(2, N+1):
    if x[i] :
        if i >= M:
            print(i)
        for j in range(i+i,N+1,i) :
            x[j] = False

  그래서 구현된 답은 위와 같다. 0번째와 1번째 인덱스를 False로 두고 N번째 인덱스까지 모두 True로 리스트를 만들고 시작한다. for구문은 2부터 시작하며 True이면 범위안에 들어가는지를 먼저체크하고 범위안에 들어가면 출력한다. 그리고 범위와 무관하게 True이면 배수로 있는 인덱스에 대한 값은 모두 False로 변경한다.

 

 위와 같이 했더니 제한시간이 2초임에도 불구하고 약 0.5초로 끝낼 수 있었다.

 

 

 

---

 

 

참고

1929번: 소수 구하기