2581번: 소수(백준 C++)

소수

문제

자연수 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

입력
60
100

출력
620
61

예제 입출력2

입력
64
65

출력
-1

---

코드

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

// 소수를 판별하는 함수, 소수라면 1을, 소수가 아니라면 0을 return한다.
int judge_prime(int n){
  if(n == 1) return 0;

  for(int i=2; i <= sqrt(n); i++)
    if(n%i == 0) return 0;

  return 1;}

int main(){
  int n1, n2; //소수판별할 범위의 시작과 끝, n1~n2
  int sum = 0; //범위 내 소수의 합
  int min = 10001;// 범위 내 소수의 최소값.
  bool arr[10001] = {0,}; // 1~10000까지의 배열, 배열의 값이 0이면 소수이고, 1이면 소수가 아니다.

  cin >> n1 >> n2; //범위 설정

  for(int i=n1; i <=n2; i++){
    // 배열의 값이 1-> 소수가 아니므로 다음값으로 바로 간다.
    if(arr[i] == 1) continue;

    // 소수라면?
    if(judge_prime(i)){
      // sum에 값을 추가하고, 최소를 판별하여 넣는다.
      sum += i;
      min = i < min ? i : min;

      //소수의 배수는 소수가 아니다. 그러므로 소수의 배수는 배열의 값을 1로 바꿔주어 판별하지 않는다.
      for(int j=1; i*j<=10000; j++ ){
        arr[i*j] = 1;
      }
    }
  }
 // 값 출력.
  if(sum)
    cout << sum << "\n" << min;
  else
    cout << -1;
}

사견이자 해석

어제 풀었던 1978번과 유사하다. 다만 이번에는 연속적인 수의 나열에서 소수를 찾아내는 문제이다.

따라서 가장 작은 수부터 탐색을 시작해서 소수인지 아닌지 판별을 한다.

소수 판별 함수

// 소수를 판별하는 함수, 소수라면 1을, 소수가 아니라면 0을 return한다.
int judge_prime(int n){
  if(n == 1) return 0;

  for(int i=2; i <= sqrt(n); i++)
    if(n%i == 0) return 0;

  return 1;}

위 함수의 Return 값이 1, 즉 소수라면
그 수의 배수들은 소수가 아니라는 뜻이다. 그렇기 때문에 미리 판별 대상에서 제외를 해 주는 작업을 한다.

   //소수의 배수는 소수가 아니다. 그러므로 소수의 배수는 배열의 값을 1로 바꿔주어 판별하지 않는다.
      for(int j=1; i*j<=10000; j++ ){
        arr[i*j] = 1;
      }

이렇게 하면, 판별해야할 대상들은 반복문이 반복될수록 적어지면서 값 도출의 시간을 줄일 수 있다.