백준 1929번 소수 구하기

1. 문제 설명

문제링크

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

• 입력
  • 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
• 출력 :한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

2. 코드

import sys

input = sys.stdin.readline

# 1000000(백만) 이하의 자연수 이다.
p = 10 ** 6

# 0, 1 은 소수가 아니므로 리스트 형태에서 False 표시 해준다.
# 이후 2 ~ 1000000(백만) 까지 모든 숫자들은 True 표시 해둔다.
# 이때 p - 1 를 한 이유는 앞서 0, 1 의 길이 즉 2만큼 소수가 아님을 표시 해줬기 때문이다.
# 그래서 p - 1 의 길이 만큼만 True 표시를 해주면 길이는 1000001 이다.
prime = [False, False] + [True] * (p - 1)

# 에라토스테네스의 체를 이용한 방식이다.
# i 값의 범위를 10 ** 6 절반인 10 ** 3 까지만 돌려도 된다.
for i in range(1, int(p ** 0.5) + 1):
    # 소수인지 판별!!
    if prime[i]:
        # 만약 i 가 소수라면 i의 배수들은 소수가 아님을 이용한 반복문이다.
        for j in range(2 * i, p + 1, i):
            prime[j] = False

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

for i in range(m, n + 1):
    if prime[i]:
        print(i)

3. 회고

Q. 문제를 보고 든 생각

• 에라토스테네스의 체를 이용하여 소수를 판별 하고자 했다.
• 일반적인 소수 판별 시간복잡도는 O(N)값이다. 하지만 판별하고자 하는 소수의 범위의 제곱근 값 즉, n = 10000, n의 제곱근인 100 까지를 이용하여 소수 판별하는 알고리즘의 시간복잡도는 O(N^(1/2)) 이지만 여전히 n 값이 크면 시간복잡도가 상당히 높은것을 나타 낼수 있다.
• 이를 보완하고자 나온 알고리즘이 에라토스테네스의 체이다.
• 이를 이용하여 문제를 풀어보고자 했다.

4. 고쳐야 할점

더 좋은 방법이 있다면 댓글로 알려주세요!!!