BOJ - 1978 소수 찾기

 

해결방법

소수를 찾는 함수 알고리즘을 이용하여 구한다.

소수는 2 이상의 자연수이고, 1과 자기 자신을 제외하고는 다른 수에 의해 나누어 떨어지지 않는 수를 의미한다.

즉, 어느 수가 소수인지 확인하려면 그 수의 제곱근까지만 소수를 나누어보면 된다.

만약 어떤 수의 제곱근값까지 도달하기 전까지 나누어진다면 그 수는 소수가 아닌 것이다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

bool isPrime(int num)
{
    if (num < 2)
        return false;

    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int N, primeCount = 0;
    cin >> N;

    vector<int> array(N);

    for (int i = 0; i < N; i++)
    {
        cin >> array[i];
    }

    for (int i = 0; i < N; i++)
    {
        if (isPrime(array[i]))
        {
            primeCount++;
        }
    }

    cout << primeCount << endl;

    return 0;
}