https://www.acmicpc.net/problem/2581
시간 2초, 메모리 128MB
input :
- M
- N
- M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.
output :
- M이상 N이하의 자연수 중 소수인 것을 모두 찾아
- 첫째 줄에 그 합
- 둘째 줄에 그 중 최솟값을 출력
- 소수가 없을 경우는 첫째 줄에 -1을 출력
모든 수를 에라토스테네스의 체를 이용해서 분류를 하고,
나중에 m에서 n 범위 까지에서 소수를 판별해 ret리스트에 저장을 하도록 한다.
최솟값의 경우엔 제일 앞 0번쨰 인덱스에 존재한다.
import sys
from math import sqrt
prime_number = [1] * 10001
prime_number[0] = prime_number[1] = 0
for i in range(2, int(sqrt(10001))):
for j in range(i * i, 10001, i):
if prime_number[j]:
prime_number[j] = 0
ret = []
m = int(sys.stdin.readline())
n = int(sys.stdin.readline())
for i in range(m, n + 1):
if prime_number[i]:
ret.append(i)
if len(ret) <= 0:
print(-1)
else:
print(sum(ret))
print(ret[0])
