[BAEKJOON] 1929번: 소수 구하기

문제

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

 

코드

import sys

input = sys.stdin.readline

max_ = 1_000_000
check = [0] * (max_+1)
check[0], check[1] = True,True
for i in range(2, max_):
    j = i + i
    while j <= max_:
        check[j] = True
        j += i

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

[print(i) for i in range(n, m+1) if not check[i]]

 

나의 생각

리스트 컴프리헨션을 사용하면 한 줄로 간결하고 빠르게 작성할 수 있지만 큰 데이터를 다룰 때는 메모리 사용이 늘어날 수 있다.

그리고 위의 코드는 1부터 max_까지의 소수를 모두 다 구하니까 효율적이지 못하다.

우리한테 필요한거는 1부터 m까지의 소수이다. 

이것을 참고해서 코드를 다시 짜보면

import math, sys
input = sys.stdin.readline

n, m = map(int, input().split())
# 0부터 n까지의 소수 체크하기
prime = [True for _ in range(m+1)]
prime[0] = prime[1] = False
for i in range(2, int(math.sqrt(m))+1):
    if prime[i] == True:
        for j in range(2, m//i + 1):
            prime[i*j] = False
for i in range(n, m+1):
    if prime[i] == True:
        print(i)

훨씬 더 빨리 동작하는걸 볼 수 있다.