[baekjoon] 백준 1929번(파이썬): 소수 구하기

문제

1929번: 소수 구하기

알고리즘

-  일반적으로 소수를 구하는 방법으로 구하게 되면 시간 복잡도가 O(n^2)이고 에라토스테네스의 체를 통해 구하게 되면  시간 복잡도가 O(log n)이다.

- 따라서 에라토스테네스의 체를 통해 소수를 구한다.

- 구한 소수가 범위 내에 있다면 출력한다.

코드

import sys

m, n = map(int, sys.stdin.readline().split())
dp = [False, False] + [True] * 1000001
primes = []

# 에라토스테네스의 체를 통해 소수를 구한다.
for i in range(2, n+1):
    if dp[i]:
        primes.append(i)
        for j in range(i*2, n+1, i):
            dp[j] = False


# 구한 소수가 범위 내에 있다면 출력
for i in primes:
    if i > n:
        break

    if i >= m:
        print(i)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법