[2581] 소수 Success

문제

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

---

소수란? 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 1이 아닌 자연수.

이전 [1978]소수 찾기 문제에서 사용한 function과 추가적으로 최소 소수 구하는 function, 소수의 합을 구하는 function 총 세 개를 구현 하였습니다.

boolean findPrime(int N)

• input: 정수 N
• output: 소수일 경우 true, 소수가 아닐 경우 false

  for (int i = 2; i <= Math.sqrt(N); i++) {
    if(N%i==0) {
        return false;
    }
  }
  

int findSumOfPrimeNumber(int M, int N)

• input: 정수 범위 M, N
• output: 범위 내의 소수들의 합

  int sum = 0;
  for (int i = M; i <= N; i++) {
    if (findPrime(i)) {
        sum += i;
    }
  }
  return sum;
  

int findMinPrimeNumber(int M, int N)

• input: 정수 범위 M, N
• output: 범위 내의 최소 소수

  for (int i = M; i <= N; i++) {
    if (function(i)) {
        return i;
    }
  }
  return -1;
  

최소 소수와 소수들의 합을 구하는 함수를 하나로 구현해 한 번만 순회하여 구현할 수도 있었지만 함수의 기능을 최소화하고 싶어 둘로 나누었습니다.

다행히 성능 문제 없이 통과 가능했습니다.

감사합니다.

Text by Chaelin. Photographs by Unsplash.

---