[파이썬, Python] 백준 1929: 소수 구하기

문제

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

코드

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

for i in range(m,n+1):
    if i == 1:
        continue
    for j in range(2, int(i**0.5)+1):
        if i%j == 0:
            break
    else:
        print(i)

설명

앞선 문제들은 에라토스테네스의 체를 이용하지 않고도 시간초과가 나지 않아서 진행했는데,
이 문제의 경우 이용하지 않으면 시간초과의 늪에서 벗어날 수 없었다.

에라토스테네스의 체는 소수를 판별하기 위한 방법인데,
자세하게 설명하면 너무 수학적인 내용이라 어려워지므로 사용법만 알아보고 가자.

우선 수를 입력받고,
1이면 continue 해준다.

이후 2부터 i의 제곱근까지(자세한 설명은 구글을 이용해 보자)의 수를 판별하는데,
만약 0으로 나누어지는 수가 있다면(자기 자신 이외의 수로 나누어졌다면),
반복문을 탈출한다.

이후 조건문을 다 통과한 수는 소수이므로 출력해 준다.