BOJ - 2581번 소수 (Python)

문제 출처: https://www.acmicpc.net/problem/2581

문제 난이도

Silver 4

문제 접근법

N 최대 수가 10,000이길래 에라토스테네스의 체를 사용했다.

통과 코드

import math


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


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

arr = is_prime(M)
res = []

for i in range(N, M+1):
    if arr[i] == True:
        res.append(i)

if len(res) == 0:
    print("-1")
else:
    print(sum(res))
    print(res[0])