(백준 알고리즘 문제풀이)2581번 소수

문제

문제 링크

 

문제 접근

• 에라토스테네스의 체 알고리즘 사용
• 에라토스테네스 위키피디아

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

코드

import sys
input = sys.stdin.readline

m = int(input())
n = int(input())

# 에라토스테네스 알고리즘
dp = [True for _ in range(n+1)]

for i in range(2, n+1):
    if dp[i]:
        j = 2
        while i * j <= n:
            dp[i * j] = False
            j += 1


result = list()
for i in range(m, n+1):
	# True이고 1이 아닐 경우에 소수
    if dp[i] is True and i != 1:
        result.append(i)


# 출력
if result:
    print(sum(result))
    print(min(result))
else:
    print(-1)