백준 1929번 : 소수 구하기

문제

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

---

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) 

M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

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

---

예제 입력 1

3   16

예제 출력 1

3
5
7
11
13

---

해결 방법

에라토스테네스의 체를 이용해서 해결하였다.

에라토스테네스의 체 알고리즘

• 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘
• 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용
• 에라토스테네스의 체 알고리즘의 구체적인 동작 과정은 다음과 같다.

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

에라토스테네스의 체 알고리즘의 시간 복잡도는 사실상 선형 시간에 가까운 정도로 매우 빠르다.

시간 복잡도 : $$O(NloglogN)$$

에라토스테네스의 체 알고리즘은 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있다.

하지만 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다.

10억이 소수인지 아닌지 판별할 때 에라토스테네스의 체를 사용할 수 있을까? => 메모리 측면에서는 비효율적 !

 

#나동빈 강의 참고
import math

n = 1000 #2부터 1000까지의 모든 수에 대하여 소수 판별
#처음엔 모든 수가 소수(True)인 것으로 초기화 시킴
array = [True for i in range(n+1)]

#에라토스테네스의 체 알고리즘 수행
#2부터 n의 제곱근까지의 모든 수를 확인
for i in range(2, int(math.sqrt(n)) + 1):
	if array[i] === True: #i가 소수인 경우(남은 수인 경우)
    	#i 를 제외한 i의 모든 배수를 지우기
        j = 2
        while i*j <= n:
        	array[i*j] = False
            j += 1
#모든 소수 출력
for i in range(2,n+1):
	if array[i]:
    	print(i, end=' ')

 

PyPy3로 실행시켰고  메모리 : 131380 KB   시간 : 180ms

계속 시간 초과가 떴었는데, 에라토스테네스의 체 알고리즘을 사용하지 않고 소수를 구하게 되면 시간 초과가 발생하게 된다.

소스 코드

A, B = map(int,input().split())

def isPrime(A,B):
    prime = [True] * B
    for i in range(2, int(B**0.5)+1):
        if prime[i]:
            for j in range(2*i, B, i):
                prime[j] = False
    for i in range (A,B):
        if i > 1 and prime[i] == True:
            print(i)
            
isPrime(A, B+1)