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

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

1929번: 소수 구하기

문제

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

입력

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

출력

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

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

풀이

설명

• '1978번 소수 찾기' 문제와 비슷한 로직으로 풀면 되는데 똑같이 풀면 안 된다.
• 같은 방식으로 풀 경우, 시간 초과가 발생한다.
• 이를 해결하기 위해, input() 부분과 range 안에서의 범위를 수정해주어야 한다.
  • input() -> sys import로 변경
  • range 범위 : A -> A**0.5 + 1
    • '에라토스테네스의 체' 활용
      1. 2부터 N까지 모든 수를 써놓는다.
      2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
      3. 그 수는 소수이다.
      4. 그 수의 배수를 모두 지운다.

코드

• 시간 초과 해결 전

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

def prime(A : int) :
    if A < 2 :
        return False
    for i in range(2, A) :
        if A%i == 0 :
            return False
    return True

for i in range(M, N) :
    if prime(i) :
        print(i)

• 시간 초과 해결 후

import sys

M, N = [int(x) for x in sys.stdin.readline().split()]

def prime(A : int) :
    if A < 2 :
        return False
    for i in range(2, int(A**0.5) + 1) :
        if A%i == 0 :
            return False
    return True

for i in range(M, N+1) :
    if prime(i) :
        print(i)