백준 - 소인수분해(11653)

문제

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

• 입력

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

• 출력

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

• 예제 입력 1

3 16

• 예제 출력 1

3
5
7
11
13

---

• 첫번째 시도

m, n = map(int, input().split())
sosu = []
for num in range(m,n+1):
    errorFlag = 0
    if num > 1:
        for i in range(2,num):
            if num % i == 0:
                errorFlag += 1
                break
        if errorFlag == 0:    
            sosu.append(num)
for answer in sosu:
    print(answer)

• 정답

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)

---

• 문제해설

1은 소수가 아니므로 제외해준다.
반복문을 돌린다. 범위는 2부터 int(i**0.5)+1까지이다. 특정 수의 제곱근을 구해, 그 제곱근까지의 약수를 구하면 해당 약수를 포함하는 수를 모두 제거할 수 있다(소수가 아니기에). 이렇기 때문에 범위를 위와같이 설정해주었다.
예를들어, i=12에서 12의 약수는 1 2 3 4 6 12
int(sqrt(12))=3이고 12는 3으로 나누어 떨어지므로 더 검사할 필요가 없다.
i가 j로 나누어떨어지므로 약수가 존재한다. 고로 소수가 아니고, 해당 제곱근(j)이상의 숫자에 대해 더이상 검사할 필요가 없으므로 멈춘다.
i가 1이 아니라면 해당 숫자를 출력해준다.

• 에라토스테네스의 체

에라토스테네스의 체에서는 1을 제거 
--> 지워지지 않는 수 중에 제일 작은 2를 소수로 선택한다 
--> 나머지 2의 배수를 모두 지운다 
--> 지워지지 않는 수 중에 제일 작은 3을 소수로 선택한다 
--> 나머지 3의 배수를 지운다 
... 5, 7, 11, 13 등으로 반복을 한다.
이런 식으로 처리가 되고, 이런 일련의 과정을 해나가면 다음과 같이 나온다.

참고한 블로그 링크1
참고한 블로그 링크2