[230110] 백준 1929번 - 소수 구하기 (Python)

https://github.com/cjk09083/Code

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

1929번: 소수 구하기

 

문제

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

입력

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

출력

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

 

해답)

if __name__ == "__main__": 
    start, end = map(int,input().split())

    fList = [0] * (end+1)
    fList[1] = 1

    for i in range(2, end+1):
        if fList[i]==1:
            continue

        if start  <= i <= end:
            print(i)
        for j in range(2, (end//i)+1):
            fList[i*j] = 1

- 만약 n보다 작은 어떤 수 m이 m = ab라면 a와 b중 적어도 하나는 sqrt(n) 이하이다.

- n보다 작은 합성수 m은 sqrt(n)보다 작은 수의 배수만 체크해도 전부 지워지므로 , sqrt(n)하의 수의 배수만 지우면 된다.