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])
Author And Source
이 문제에 관하여(BOJ 2581 소수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-2581-소수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)