[백준 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을 출력한다.

 

 

나의 풀이

 

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

int isPrime(int n) {  							//소수 판별 함수
    if (n == 1) return 0;
    else if (n <= 3) return 1;
    else {
        for (int i = 2; i <= sqrt(n); i++)
            if (n % i == 0)
                return 0;
    }
    return 1;
}

int main(void) {

    int m, n, min, sum = 0;
    scanf("%d %d", &m, &n);

    for (int i = n; i >= m; i--) {			//min값 저장을 위해 역순으로 내려가기
        if (isPrime(i)) {
            sum += i;
            min = i;
        }
    }
    
    if (sum == 0) {							//소수가 없었을 경우 -1출력
        printf("-1");
    }
    else {							//소수가 있었을 경우 그 합과 최솟값 출력
        printf("%d\n", sum);
        printf("%d", min);
    }

    return 0;
}

매우 자주 나오는 소수 관련 알고리즘이다. 

n의 소수 여부를 판별할 때, i부터 n까지 나눠서 나머지가 0이면 소수가 아니라고 판별하는 방법을 많이 사용하는데 

이 때 n의 제곱근까지만 나눠주면 속도가 매우 빨라진다. 

제곱근을 구하는 함수는 math.h의 sqrt()이므로 잘 활용하면 좋다. 

 

문제에서는 소수의 누적합뿐만 아니라 최소 소수까지 구하라고 했으므로, 

n~m까지 역순으로 내려가며 소수를 판별,

소수면 합에 누적하고 min에 업데이트해준다. 

 

이후 sum==0, 즉 소수가 없었으면 -1을 출력하고 

소수가 있었으면 sum, min을 출력하면 끝.