[백준] 소수 구하기 (Python)

✏️ 문제

1929번: 소수 구하기

✏️ 풀이

소수는 1을 제외하고, 1과 자기자신으로만 나눠지는 수를 의미한다.

보통은 2부터 자기 자신까지 수를 증가시켜가며 나머지가 0이 되는 경우가 있는지 살펴봐야 하지만

이 문제에서는 그렇게 풀이하면 시간초과가 난다.

따라서 반복문의 횟수를 줄여줘야 한다.

예를 들어 20의 경우, 1*20, 2*10, 4*5, 5*4, 10*2, 2*10 이므로

20^1/2 이후로는 동일한 수가 나타나는 것을 볼 수 있다.

따라서 반복문도 n^1/2까지만 돌면 된다.

이외에도 에라토스테네스의 체를 구현하여도 문제를 해결할 수 있다.

에라토스테네스의 체는 2의 배수, 3의 배수,, 를 순차적으로 제거하는 방식이다.

✏️ 코드

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

for i in range(M, N+1):
    if i == 1:
        continue
    for j in range(2, int(math.sqrt(i)+1)):
        if i % j == 0:
            break
    else:
        print(i)