[BAEKJOON] 1978번

#include <stdio.h>
 
int is_prime(int n);
 
int main()
{
    int n;
    int i;
    int count = 0;
    int lim;
 
    scanf("%d", &lim);
 
    for (i = 0; i < lim; ++i)
    {
        scanf("%d", &n);
        if (is_prime(n)) { ++count; }
    }
    
    printf("%d\n", count);
    
    return 0;
}
 
int is_prime(int n)
{
    int i;
 
    if (n != 2)
    { 
        if ((n % 2) && (n != 1)) //Odd
        {
            for (i = 3; i*i <= n; i += 2)
            {
                if (n%i == 0) { return 0; }
            }
        }
        else { return 0; }
    }
 
    return 1;
}

 lim 번 입력받고, 입력받은 수가 소수인지  is_prime  함수로 검사한다.

 is_prime  함수는 2를 예외 처리하고 1이 아닌 홀수에 대해서 소수인지 검사한다.

이 때 반복은  i*i 의 값이  n 이 될 때까지, 즉  i=√n 이 될 때까지 반복한다(Eratosthenes`s sieve). 그리고  i=3 부터 시작해  2 씩 더해 연산 횟수를 절반으로 줄인다.