Math_06_소수(2581)
Math06소수(2581)
문제
자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.
자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.
예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.
입력
입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.
M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.
출력
M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.
풀이
- arr배열 1부터 a와 b 중 max값 까지 0으로 초기화
- 2부터 a와 b 중 max값 까지 0이면 res배열에 값 추가
- 값을 추가한 것의 arr배열 1로 초기화
- 계속해서 처음이 0인 값(즉 소수)은 res에 추가, 그 값의 배수들은 arr에 1로 초기화
- slice 기능으로 a 부터 b까지 자름
- 자른 것 배열 값 for 문으로 확인하여 0이 아니면 min값 비교해서 저장 & sum 값 누적
코드
import sys
sys.stdin = open("input.txt","rt")
def input():
return sys.stdin.readline().rstrip()
a =int(input())
b =int(input())
N = max(a,b)
sum = 0
res = [0]*(N+1)
arr= [0]*(N+1)
minNum = 2147000000
for i in range(2,b+1):
if arr[i]==0:
res[i] = i
for j in range(i,N+1,i):
arr[j] = 1
res = res[min(a,b):max(a,b)+1]
if max(res) == 0:
print(-1)
exit()
for x in res:
if x != 0:
sum += x
if x < minNum:
minNum = x
print(sum)
print(minNum)
배운 것
소수 찾는 법은 배수에 check하는 데에 있다
코멘트
Author And Source
이 문제에 관하여(Math_06_소수(2581)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@angel_eugnen/Math06소수2581저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)