1978번. 소수 찾기 - C++

문제 링크

소수 찾기

코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n, a, cnt = 0;
    bool isPrime;
    cin >> n;

    for (int i = 0; i < n; i++) {
        isPrime = true;
        cin >> a;
        if (a == 1) continue;
        
        for (int j = 2; j <= sqrt(a); j++) {
            if ((a % j) == 0) {
                isPrime = false;
                break;
            }
        }
        
        if (isPrime) {
            cnt++;
        }
    }
    
    cout << cnt;

    return 0;
}

설명

1. n개의 수를 입력받아서 저장한다.
2. 각 숫자를 2부터 그 숫자의 제곱근까지 반복문으로 나누어 본다. 만약 중간에 약수가 나오면 isPrime을 false로 설정하고 break 한다.
3. isPrime이 true면 cnt를 증가시키고 다음 숫자로 넘어간다.

왜 제곱근까지만 나누는가?

수학적으로 접근하면 알 수 있다. 24를 예로 들자. 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24이다.
약수끼리 짝지어서 곱하여 24를 만든다 치면 (1, 24), (2, 12), (3, 8), (4, 6)이 나온다.
24의 제곱근은 대략 4.8989…가 나온다.

1, 2, 3, 4, 4.8989... 6, 8, 12, 24
여기서, 약수끼리 짝지을 때 그 숫자의 제곱근을 중심으로 대칭을 이룬다는 점을 알 수 있다.

따라서 제곱근 이후엔 어차피 약수가 있다는 뜻이 되므로, 제곱근 전까지만 반복문을 돌리면 된다.
이런 경우엔 시간 복잡도가 \(O(\sqrt{n})\)이 된다.

참고 블로그

출처