[백준 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.....