[백준 1929번] 소수 구하기(파이썬)

문제

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

 

입력

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

출력

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

 

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

 

---

 

풀이

주어진 수 2개 사이에 소수를 하나씩 출력하면 되는건데요.
그렇다면 모든 수를 돌면서 1을 제외한 나누어 떨어지는 수가 있는지 없는지 확인하면 되네요.

하지만 이렇게 모든 수를 확인 하다보면 시간초과가 발생합니다.
시간초과를 해결하기 위해서 모든 수를 확인하는 방법보다
제곱근을 사용해서 모든 수의 절반만 확인하고 소수를 찾을 수 있어요.

만약 숫자가 18이라면 18의 약수는
1, 2, 3, 6, 9, 18
1x18, 2x9, 3x6 으로 서로 대칭이 됩니다.
그래서 이 경우에는 3까지만 확인하면 나누어 떨어지는 수가 있는 걸 확인 할 수 있네요.

18의 제곱근은 18**0.5 = 4.xx 이고, 제곱근보다 같거나 작은 수까지만 나눠보고,
나누어 떨어지는게 있는지 없는지 확인하면 됩니다.

만약 숫자가 30이라면
1, 2, 3, 5, 6, 10, 15, 30
1x30, 2x15, 3x10, 5x6 으로 대칭이 됩니다.
이 경우에는 5까지만 확인하면 되겠네요.
30의 제곱근은 30**0.5 = 5.xx 이고, 5보다 작거나 같은 수까지 확인하면 됩니다.

코드를 순서대로 작성한다면
1. 2개의 자연수 입력
2. 2개의 자연수 이상, 이하 값을 하나씩 확인
3. 1은 소수에서 제외
5. 2 ~ 제곱근 사이 나누어 떨어진다면 종료 > 다음 수 확인
6. 나누어 떨어지지 않거나 for문이 끝난다면 다음 else문에 해당 값 출력

※ for - else문 : for문이 실행되고 난 다음 else문이 실행된다. for문에 break를 사용했을 때 else문 실행 X

---

작성 코드

N, M = map(int, input().split())

for i in range(N, M+1):
    if i == 1: # 1은 통과
        continue
        
    for j in range(2, int(i**0.5) + 1): # 2 ~ 제곱근 사이 값 확인
        if i % j == 0: # 나누어 떨어진다면 그대로 종료 (else문 실행 X)
            break
    else: # for문이 잘 실행이 되었다면 print(i) 출력
        print(i)