[백준(BOJ)] 2581번 소수, C언어 풀이

<소수>, 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을 출력한다.

 

예제 입력 1

60

100

예제 출력 1

620

61

예제 입력 2

64

65

예제 출력 2

-1

 

풀이

이 문제는 자연수 M과 N을 입력한 후 M부터 N까지의 소수의 합과 최솟값을 출력하도록 해야 하는데, 추가적인 조건으로 만약 M부터 N까지의 수 중에서 소수가 하나도 포함되어 있지 않다면 첫째 줄에 –1을 출력하는 프로그램을 제작하는 것이다. 나는 먼저 자연수 M과 N을 입력하도록 했고, 다음에 for문을 돌려서 M부터 N까지의 수를 확인하도록 했다. 그리고 이중 for문을 돌려서 M부터 N까지의 수가 소수인지 체크해 소수라면 합을 더하도록 하고 또한, first 변수 또한 값을 증가시키도록 해 if문을 사용해서 first값이 1일 경우가 소수의 최솟값이므로 이를 변수 min에 저장시켜 최솟값을 구했다. 최종적으로는 if문을 사용해서 M부터 N까지의 소수의 합이 0이라면 소수가 하나도 존재하지 않는 것이기 때문에 –1을 출력하도록 했고, 소수의 합이 0이 아니라면(else)를 사용해서 첫째 줄에 소수의 합, 두 번째 줄에 소수의 최솟값을 출력하도록 프로그램을 제작했다.

 

#include <stdio.h>

int main(void)
{
    int N, M;
    int first = 0, min = 0, sum = 0;
    scanf("%d", &M);
    scanf("%d", &N);

    for (int i = M; i <= N; i++)
    {
        for (int j = 2; j <= i; j++)
        {
            if (i % j == 0)
                if (i == j)
                {
                    sum += i;
                    first++;
                    if (first == 1)
                        min = i;
                    break;
                }
                else
                    break;
        }
    }
    if (sum == 0)
        printf("-1");
    else
        printf("%d\n%d", sum, min);

    return 0;
}