[Python] 소수

문제

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

예제 입력

60
100

 

예제 출력

620
61

예제 입력

64
65

 

예제 출력

-1

 

---

문재 해결 방법

• n, m의 소수를 계산하고 리스트에 저장해줍니다
• 리스트를 통해 최소값, 그리고 합을 출력하면 됩니다.
• 주의
  • M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력해야합니다.
  • 제가 이 부분을 잊고 제출하고 틀렸습니다..
   

코드 해석

• n, m 을 입력 받습니다.
• primes 리스트를 생성하여 소수를 저장하기 위해 사용하였습니다.
• if num < 2:
  • num(현재)재 숫자가 2보다 작으면 소수가 아니므로 건너뛰도록 하였습니다.
  • 왜냐하면 1은 자기 자신의 값만 가지고 있기 때문입니다.
• is_prime변수를 사용하여 현재 숫자가 소수인지 판별할 수 있도록 하였습니다.
• for i in range(2, int(num**0.5)+1):
  • 일반적으로 저희가 소수를 판별할 때 숫자의 제곱근까지만 확인하면 됩니다.
  • 예를 들어서, 만약 숫자 60이 들어왔다고 가정을 하면 60을 제곱근하면 7.746입니다.
  • 즉 60을 판별하기 위해서는 2부터 7까지 약수인지 확인하면 됩니다.(2 ~ 7까지 60을 나누어진다면 소수가 아닙니다.)
• 만약 해당 숫자가 소수인 경우에는 primes 리스트에 해당 숫자를 추가합니다
• 모든 숫자를 확인한 후, primes 리스트가 비어있는지 확인합니다. 만약 비어있다면 소수가 없는 것이므로 -1을 출력합니다.
• 비어 있지 않으면, 해당 소수 리스트의 합계와 최솟값을 반환하도록 하였습니다.

 

 

출처: 백준 https://www.acmicpc.net/problem/2581