[파이썬] 1929 : 소수 구하기

문제

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

입력

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

출력

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

예제 입력 1 복사

3

16

예제 출력 1 복사

3

5

7

11

13

---

에라토스테네스의 체를 사용하였다.

 

이전에 조금 비효율적인 풀이를 사용하여 시간초과가 났었다.

 

하지만 bool 타입으로 소수 유무를 판단하는식으로 다른 풀이를 작성했고, 시간 제한을 통과하였다.

 

바로 아래 코드를 보자.

import math

#시간초과
def solve(m, n):

    resultList = list(range(m, n+1))
    #에라토스테네스의 체 에서는 2부터 n의 제곱근까지의 수를 확인하기때문에 n의 제곱근까지 리스트 하나 만들어줌
    sqrtList = list(range(2, math.ceil(math.sqrt(n))+1))


    for i in sqrtList:
        for value in resultList:
            if value//i==1:
                pass
            elif value%i==0:
                # sqrtList.remove(i)
                resultList.remove(value)

    print(*resultList, sep="\n")

#다른풀이
def otherSolve(m, n):
    #index => 숫자, value => 소수인지 아닌지?
    resultList = [True for _ in range(n+1)]
    #0과 1은 소수가 될 수 없음
    resultList[0] = False
    resultList[1] = False

    # 에라토스테네스의 체
    # 2부터 n의 제곱근까지의 모든 수를 확인하며, i가 소수인 경우 i를 제외한 모든 배수를 지우도록 한다.
    for i in range(2, math.ceil(math.sqrt(n))+1):
        if resultList[i]:
            #i를 제외한 모든 i의 배수 지우기
            for delt in range(i*2, len(resultList), i):
                resultList[delt] = False

    #출력부
    for i in range(m, n+1):
        if resultList[i]==True:
            print(i)

if __name__ == "__main__":
    a, b = map(int, input().split(" "))
    otherSolve(a, b)