[C++] BOJ 1978 소수 찾기

문제 출처

백준 온라인 저지

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

1978번: 소수 찾기

 

문제 

 

입 / 출력

 

풀이

에라토스테네스의 체 알고리즘을 사용해서 소수를 찾아 해결 할 수 있다.

 

코드

#include <iostream>

using namespace std;

int arr[1001] = {
    0,
};
int n, tmp, result = 0;

int main() {
  for (int i = 2; i <= 1000; i++) {
    arr[i] = i;
  }

  for (int i = 2; i <= 1000; i++) {
    if (arr[i] == 0)
      continue;
    for (int j = 2 * i; j <= 1000; j += i) {
      arr[j] = 0;
    }
  }

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> tmp;
    if (arr[tmp] != 0)
      result++;
  }
  cout << result;
}