[BOJ 1978] 소수 찾기 (C++)

소수 찾기 (Silver 4)

문제

전체 문제 보기

1978번: 소수 찾기

접근법

임의의 수 N이 소수인지 아닌지 판단하기 위해서는 \(\sqrt {N}\)까지 수를 나눠보면 알 수 있다. 예를 들어 49가 소수인지 아닌지 판단하기 위해서는 2~7까지의 수를 나눠보면 알 수 있다. 왜냐하면 임의의 수 N에서 소인수 짝은 \(\sqrt{N}\) 이하인 수 하나와 \(\sqrt{N}\) 이상인 수 하나로 구성되어 있기 때문이다. 그래서 아래와 같이 소수 판별 코드를 작성할 수 있다.

구현

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

int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N;
    int answer = 0;

    cin >> N;

    while (N--)
    {
        int number;
        cin >> number;
        if (number == 1)
        {
            continue;
        }
        if (number == 2)
        {
            answer++;
            continue;
        }

        bool isPrime = true;
        int sqrtNum = static_cast<int>(sqrt(number));
        // 2부터 sqrtNum 까지 모두 나눠서 나머지가 0인 경우가 있으면 소수가 아님.
        for (int i = 2; i <= sqrtNum; i++)
        {
            if (number % i == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
            answer++;
    }

    cout << answer;
    return 0;
}