백준 1929 문제 분석 python

🐒 소수 구하기

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

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

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

입력 예시

3 16

출력 예시

3
5
7
11
13

---

✍ 나의 풀이

def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num % i ==0:
                return False
        return True

m, n = map(int,input().split())

for i in range(m,n+1):
    if isPrime(i):
        print(i)

소수 판별 문제가 어렵다..
인터넷 검색으로 답안을 이해하면서 따라가야겠다.

---

다른 풀이 (에라토스테네스의 체)

m, n = map(int,input().split())

arr = [True for i in range(n+1)]
arr[1] = False

for j in range(2,int(n**0.5)+1):
    if arr[j] == True:
        count = 2
        while j*count <= n:
            arr[j*count] = False
            count += 1

            
for i in range(m,n+1):
    if arr[i]:
        print(i)

에라토스테네스의 체 알고리즘은
소수임이 판명난 숫자의 배수는 다음 판별에서 제외한다.

이를 통해 시간복잡도를 크게 줄일수있으나, n까지의 숫자의 소수판별 결과를 저장하기 때문에 메모리사용량이 많다.

(틀린건 모르고 1을 소수로 취급함 😅)