[BOJ 1978] 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

---

위 문제를 풀기 위해서는 '에라토스테네스의 체'를 알고 있다면 쉽게 풀 수 있다.

위 알고리즘을 통해 소수를 찾은 후 N개의 수를 입력 받으며 소수인지 아닌지 확인하면 된다.

 

'에라토스테네스의 체'의 자세한 내용은 아래 URL을 통해 볼 수 있다.

 

https://ladun.tistory.com/10?category=323065

---

#include <stdio.h>
 
int arr[1001];
 
void PrimeNumSetting()
{
 
   arr[1] = 1;
   for(int i = 2 ; i <= 1000;i++)
   {
        if(arr[i])
            continue;
 
        for(int j = i+ i; j <= 1000; j+= i)
           arr[j] = 1;
   }
}
 
int main()
{
    int N;
 
    scanf("%d",&N);
 
    PrimeNumSetting();
 
    int sum = 0;
    for(int i = 0;i<N;i++)
    {
        scanf("%d",&arr[0]);
 
        if(!arr[arr[0]])
           sum++;
    }
    printf("%d",sum);
 
    return 0;
}