1978번

1978번 - 소수 찾기

소수를 찾는 방법 (에라토스테네스의 체 배우기 전)

소수 : 약수가 1과 자신 밖에 없는 수

*첫번째 방법

2 ~ 자기자신-1 까지 다 나눠서 나누어 떨어지면 소수가 아니다.  O(N)

*두번째 방법

2 ~ 자기자신/2 까지 다 나눠서 나누어 떨어지면 소수가 아니다. O(N/2)

*세번째 방법

2~ 루트 자기자신 까지 다 나눠서 나누어 떨어지면 소수가 아니다. O(루트N)

<정답 코드>

#include<iostream>
 
using namespace std;
int checkPrimeNum(int num)
{
    if (num < 2)
    {
        return 0;
    }
 
    for (int i = 2; i*i <= num; i++)
    {
        if (num%i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
 
int main()
{
    int N;
    int ans = 0;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        ans += checkPrimeNum(tmp);
    }
 
    cout << ans << endl;
 
    return 0;
}