BOJ - 2581 소수 (C++)

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

2581번: 소수

어떻게 풀 것인가?

처음에는 소수를 판별하는 함수(2부터 n보다 작은 수로 나눠서 나머지가 0인게 중간에 있다면 소수O)

를 사용하여 풀려고 했다.

하지만, 이 방식을 사용하게 된다면 시간초과가 뜰 가능성이 매우 높다.

'에라토스테네스의 체'를 사용하여 문제를 풀 수도 있었지만,

for문의 사용을 최대한 줄여서, 연산시간을 최대한 줄일려고 노력했다.

---

소스 코드

#include <iostream>

using namespace std;

int check_primeNum(int n);

int main(void) {
    int M; //min
    int N; //max
    int sum = 0; //합
    int min = -1;
    int k = 0;

    cin >> M;
    cin >> N;

    for (int i = M; i <= N; i++) {
        if (check_primeNum(i) == 1) {
            if (k == 0) { // 처음 한번만 실행가능 하다(최소의 소수 값)
                min = i; //가장 작은 소수
                k = 1;
            }
            sum = sum + i; //sum에 소수를 계속 누적한다.
        }
    }

    if (sum == 0) { // 소수가 없으면
        cout << min << endl;
    } else {
        cout << sum << endl;
        cout << min << endl;
    }
}

/*소수 판별 함수*/
int check_primeNum(int n) {
    if(n == 1) //1은 소수가 아님
        return 0;
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return 0; //소수 아님
    }
    return 1; //소수임
}

---

시간 복잡도

이중 for문이 사용되었기 때문에,

O(n^2)

이라고 볼 수 있다.

---

'에라토스테네스의 체'를 공부하자