[백준/수학] 1929 소수구하기(Python, 파이썬)

www.acmicpc.net/problem/1929  

1929번: 소수 구하기

 

 

1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.

 

에라토스테네스의 체

1. 2부터 N까지 모든 수를 써 놓는다.

2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

3. 그 수는 소수이다.

4. 이제 그 수의 배수를 모두 지운다.

 

이 문제를 해결하기 위해서는 배열이 필요하다.

- 수를 지웠는지 아닌지 기록하는 배열

• 지움: True
• 지우지 않음: False

 

import sys
input=sys.stdin.readline
MAX=1000000

check=[0] * (MAX+1)
check[0] = check[1] = True

for i in range(1, MAX+1):
    if not check[i]:
    	# i의 배수를 지워간다
        j=i+i
        while j <= MAX:
            check[j] = True
            j += i

a, b = map(int, input().split())

for i in range(a, b+1):
    if not check[i]:
        print(i)