[02581] 소수

[02581] 소수

문제

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

using namespace std;

/* 함수 */
// 3 이상의 홀수 num에 대하여 소수인지 판별
bool isPrimeNum(int num) {
    for(int i = 3; i * i <= num; i += 2) { // √num 까지만 확인
        if(num % i == 0) return false; // 소수가 아닌 경우 false 반환
    }
    return true; // 소수인 경우 true 반환
}

/* main */
int main() {
    /* 변수 정의 */
    // sum: M, N 사이의 소수들의 합
    // min: 소수들 중 가장 작은 수
    int M, N, sum = 0, min = 0;

    scanf("%d%d", &M, &N);


    /* 과정 */
    // N = 1인 경우: 소수가 없음
    if(N == 1) {
        printf("%d\n", -1);
        return 0;
    }

    // M = 1인 경우 M = 2
    if(M == 1) M ++;

    // M = 2인 경우
    if(M == 2) {
        sum += M;
        min = M;
        M++; // M = 3
    }

    // M이 짝수일 경우 홀수로 만들어 줌
    if(M % 2 == 0) M++;

    // 짝수는 넘어가는 loop (M > 3인 홀수이어야 함)
    for(int i = M; i <= N; i += 2) { // M과 N 사이의 모든 홀수를 대상으로
        if(isPrimeNum(i)) { // 소수인 경우
            sum += i; // sum에 더해줌
            if(min == 0) min = i; // 최솟값이 아직 없다면 채워줌
        }
    }


    /* 결과 출력 단계 */
    // sum = 0이면 소수가 없는 경우
    // -1을 출력하고 종료
    if(sum == 0) {
        printf("%d\n", -1);
        return 0;
    }

    // 아니면 첫째 줄에 소수들의 합을, 둘째 줄에 그 중 최솟값을 출력
    printf("%d\n%d\n", sum, min);
}

부가 설명

이번 문제에서는 시간복잡도를 고려한 부분이 두 부분이 있다.
우선 소수인지 확인하는 알고리즘인 isPrimeNum에서 num을 나눈 나머지를 확인하는 과정에서 3부터 √N까지로만 나누고, 또한 홀수으로 나눠 O(N)에서 O($\frac{√N}{2}$)으로 줄였다. (정확하지는 않지만 아마 맞을 것이다....)
또한, M과 N 사이의 숫자들 중에도 홀수만 확인해 O(N)에서 O($\frac{N}{2}$) 으로 줄였다.
잠깐.. O($\frac{N}{2}$)면 큰 의미가 없는데??
전체 시간복잡도는 모르겠다

큰 의미는 없어보이지만, 최대한 빠르게 돌아가도록 시도해보았다.

출처: https://www.acmicpc.net/problem/2581