백준(BAEKJOON): 소수(2581번)

Source

문제

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

예제 출력 1

620
61

예제 입력 2

64
65

예제 출력 2

-1

해설

코드로 처리해야 할 사항은 아래 셋이다.

1. 소수 판별
2. 일정 범위 안에서 소수들의 합
3. 일정 범위 안의 소수 중 최솟값

먼저 소수 판별부터 시작해 보자. 소수에 대해서 이미 잘 알고 있다고 전제하고 소수를 판별하는 함수를 아래와 같이 구현하였다.

#include<stdio.h>
#include<math.h> 
int CheckPrime(int n);
/* 입력받은 수가 소수이면 1을, 비소수이면 0을 반환한다. */

int CheckPrime(int n)
{
    int i = 2;
    if (n == 1) return 0;

    while (1) {
        if ( i <= sqrt(n) ) {
            if ( n % i == 0 ) return 0;
            else i++;
        } else {
            return 1;
        }
    }
}

인자로 받은 수가 소수라면 1을 소수가 아니라면 0을 리턴하는 함수이다. if문의 조건으로 CheckPrime()를 주어 일정 범위 안에서 가장 작은 소수와 소수들의 합을 구한다. 소수를 누적할 변수 sum과 소수의 개수를 누적할 변수 flag를 이용하여 소수의 합계와 최소인 소수를 처리하였다.
마지막으로 출력 형식을 맞추기 위해 flag값을 이용하였다. flag가 0인 경우에는 -1을 출력하고 아닌 경우에는 계산된 합과 최소 소수를 출력한다.

소스 코드: C

#include <stdio.h>
#include <math.h>

int CheckPrime(int n);
/* 입력받은 수가 소수이면 1을, 비소수이면 0을 반환한다. */

int main(int argc, char *argv[])
{
    int m, n;
    int sum = 0, min, flag = 0;
    scanf("%d", &m);
    scanf("%d", &n);

    for (; m <= n; m++) {
        if (CheckPrime(m)) {
            sum += m;
            if ( flag == 0 ) {
                min = m;
            }
            flag++;
        }
    }

    if ( flag != 0) {    
        printf("%d\n", sum);
        printf("%d\n", min);
    } else {
        printf("-1\n");
    }
    return 0;
}

int CheckPrime(int n)
{
    int i = 2;
    if (n == 1) return 0;

    while (1) {
        if ( i <= sqrt(n) ) {
            if ( n % i == 0 ) return 0;
            else i++;
        } else {
            return 1;
        }
    }
}