백준 1929번 소수 구하기 파이썬 수학2 실버2

에라토스테네스의 체로 풀어봅시다.

에라토스테네스의 체

소수를 판별하는 알고리즘이다. 소수를 대량으로 빠르고 정확하게 구하는 방법이다.

단일 숫자 소수 여부 확인

어떤 수의 소수 여부를 확인할 때는 특정 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2) 의 시간 복잡도로 빠르게 구할 수 있다. 만약, 대량의 소수를 한꺼번에 판별해야하는 경우는 "에라토스테네스의 체"를 사용한다.

에라토스테네스의 체 원리

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워가는 방법을 이용한다.

1. 배열을 생성해 초기화한다.
2. 2부터 시작해서, 특정 수의 배수에 해당하는 수를 모두 지운다. ( 지울 때, 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다. )
3. 2부터 시작해서 남아있는 수를 모두 건너뛴다.

에라토스테네스 체의 구현

N = int(input())
number = 1000
a = list(range(1, N+1))
def find_prime(N):
	for i in range(2,N+1):
    	if a[i] ==0:
        	continue
        else:
        	for k in range(2*i,N+1,i): # 자기 자신을 제외한 그 배수는 모두 지우기
            	a[k] =0
   	for i in range(2,N+1): # 소수 출력
    	if a[i] ==0:
        	continue
        else:
        	print(a[i])
find_prime(N)

---

문제

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

입력

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

출력

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

M,N = map(int, input().split())
number = N
a = list(range(0, N+1))
def find_prime(M,N):
    for i in range(2,N+1):
        if a[i] ==0:
            continue
        else:
            for k in range(2*i,N+1,i): # 자기 자신을 제외한 그 배수는 모두 지우기
               # print(k)
                a[k] =0
    for i in range(M,N+1): # 소수 출력
        if a[i] ==0 or i ==1:
            continue
        else:
            print(a[i])
find_prime(M,N)

참고 문헌

velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4