[백준 1978] 소수 찾기

www.acmicpc.net/problem/1978

1978번: 소수 찾기

에라토스테네스의 체 개념 복습하기

 

에라토스테네스의 체?

2부터 시작해서 주어진 수 n까지 돌면서 배수를 체크해서 소수를 구하는 방법이다. 

 

#include <stdio.h>

using namespace std;

int prime[1001];

void eratos()
{
  prime[1] = 1;
  for (int i = 2; i <= 1000; i++)
  {
    if (prime[i] == 1)
    {
      continue;
    }
    for (int j = 2; j * i <= 1000; j++)
    {
      prime[i * j] = 1;
    }
  }
}
int main(void)
{
  int n;
  scanf("%d", &n);
  int result = 0;

  eratos();
  for (int i = 0; i < n; i++)
  {
    int tmp;
    scanf("%d", &tmp);
    result += prime[tmp];
  }

  printf("%d\n", n - result);
  return 0;
}