백준 1978

1978번: 소수 찾기 (acmicpc.net)

1978번: 소수 찾기

#include<stdio.h>

int main(void)
{
    int N = 0, cnt = 0;
    int arr[100]={0, };

    scanf("%d", &N);

    for(int i=0; i<N; i++)
    {
        scanf("%d", &arr[i]); 
    }

    for(int i=0; i<N; i++)
    {
        if(arr[i] == 1) // 1과 2는 따로 예외처리
            continue;
        else if(arr[i] == 2)
            cnt++;
        else if(arr[i] % 2 == 1)    // 우선적으로 홀수만 가져옴
        {
            cnt++;  // 일단 더해놓고
            for(int j=3; j<arr[i]; j++)
            {
                if(arr[i] % j == 0) // 만약 1부터 본인까지 다 나눠봤을때 나누어 떨어지는 값이 있으면
                {
                    cnt--;  // 더해줬던 cnt 감소시킴
                    break;
                }
            }
        }
    }

    printf("%d", cnt);

    return 0;
}

1과 2는 그냥 고정적으로 예외처리 해두었고, 나머지 숫자들은 우선 홀수만 먼저 걸러낸다.

먼저 cnt++로 소수의 개수를 증가시키고 홀수중에서 소수가 아닌 값이 있으면 cnt--로 다시 감소시킨다.