January 3, 2023

2581번: 소수

문제 요약

• 10,000 이하의 두 자연수 N과 M이 주어졌을 때, M 이상 N 이하 자연수 중 소수인 것을 골라 합과 최솟값을 출력
• 소수가 존재하지 않는 경우 -1을 출력
• 시간 제한 : 1초

풀이

import math

M = int(input())
N = int(input())

is_prime = [False, False] + [True] * (N - 1)

for i in range(2, int(math.sqrt(N)) + 1):
    if (is_prime[i]):
        for j in range(i * 2, N + 1, i):
            is_prime[j] = False

min = -1
sum = 0

for i in range(M, N + 1):
    if (is_prime[i]):
        sum += i
        if (min == -1):
            min = i

if (min == -1):
    print(-1)
else:
    print(sum)
    print(min)

• 에라토스테네스의 체를 이용하여 구간 내에 존재하는 소수를 구하여 해결한다.

시간 복잡도

• 해당 알고리즘은 N의 크기에 의존한다.