[백준] 2581번 :소수 - Python 파이썬

[백준] 2581번 :소수 - Python 파이썬

 

알고리즘 분류:

• 수학
• 정수론
• 소수 판정

 

링크: https://www.acmicpc.net/problem/2581

2581번: 소수

 

---

문제

자연수 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을 출력한다.

 

 

---

제출한 답

m = int(input())
n = int(input())
arr = list()
 
for num in range(m, n+1):
  #예외처리:1
  if num != 1:
    for i in range(2,int(num**0.5) + 1):
      if num % i == 0:
        break
    else:
      arr.append(num)
      
if len(arr) == 0: 
  print(-1)
else:
  print(sum(arr))
  print(min(arr))

파이썬 내장함수 sum,min을 이용함.

 

인수를 빠르게 확인하기 위해

T의 제곱근까지만 for문을 돌렸다.

 

아래는 에라토스테네스의 체를 이용한 답.

 

m,n = map(int,input().split())
 
prime = [False,False] + [True] * (n-1)
 
#에라토스테네스의 체 사용
for i in range(2,int(n**0.5)+1):
  if prime[i]:
    for k in range(i*2,n+1, i):
      prime[k] = False
 
#소수 배열 저장
arr = list()
for i in range(m,n+1):
  if prime[i]:
    arr.append(i)
 
#출력
if len(arr) != 0:
  print(sum(arr))
  print(min(arr))
else: print(-1)