백준 1978번

BOJ 1978 : 소수 찾기

에라토스테네스의 체를 이용해 non_prime 이라는 배열에 소수가 아닌 수를 체크하는 것이 중요한 부분이다.

이 문제의 풀이에서는 이미 non_prime 이 1로 존재한다면 굳이 다시 1을 대입하지 않는 조건문을 추가하지 않았으나, 그 조건문을 추가해야 중복되어 체크 (ex. 20 4x5와 5x4에서 모두 1로 대입됨) 되는 일을 막을 수 있고, 에라토스테네스의 체가 추구하는 바와 더 가까워진다.

#include <stdio.h>

int main()
{
    int N;

    int non_prime[1000] = { 0, };

    while(scanf("%d", &N) != 1) continue;

    for (int j = 2; j <= 499; j++)
    {
        for (int t = 2; t * j < 1000; t++)
            non_prime[t * j] = 1;
    }

    non_prime[0] = non_prime[1] = 1;

    int count = 0;

    for (int i = 0; i < N; i++)
    {
        int temp;
        while(scanf(" %d", &temp) != 1) continue;
        if (non_prime[temp] == 0)
        {
            count++;
        }
    }
    printf("%d", count);
}