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

문제

www.acmicpc.net/problem/1929

1929번: 소수 구하기

풀이

이전에 풀었던 베르트랑 공준과 비슷한 문제이다.

아래와 같이 소수를 구하는 방법은 O(n^2)의 시간을 가지므로 n이 최대 1,000,000이 될 수 있는 이 문제에 적합하지 않다.

# O(n^2)의 시간
n=100

def isPrime(a):
  if(a<2):
    return False
  for i in range(2,a):
    if(a%i==0):
      return False
  return True

for i in range(n+1):
  if(isPrime(i)):
    print(i)

따라서 에라토스테네스의 체를 이용하여 풀어야 한다.

 

코드

import sys

def get_prime(m, n):
    for i in range(2, n+1):
        if isPrime[i]:
            for j in range(2*i, n+1, i):
                isPrime[j] = False
    for i in range(m, n+1):
        if isPrime[i]:
            print(i)

m, n = map(int, sys.stdin.readline().split())
isPrime = [False]*2 + [True for _ in range(n-1)]

get_prime(m, n)