BOJ 2581 소수

5217 단어 2021.02.042021.02.04

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])

좋은 웹페이지 즐겨찾기