[백준 1978] 소수 찾기

백준 1978번 - 소수 찾기

백준 1978번

❓ 문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 

입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 
출력
주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1 
4
1 3 5 7
예제 출력 1
3

---

✏️ 풀이

소수(Prime Number)를 찾는 문제는 에라토스테네스의 체를 사용하면 효율이 좋다.
자세한 사항은 위키백과 - 에라토스테네스의 체 부분을 참고하면 훨씬 이해가 빠를 것이다.

쉽게 말하자면,

1. 소수를 구하고자 하는 모든 수를 나열(ex 범위 1~120).
2. 2부터 현재 수를 소수로 선택한 후, 자신의 모든 배수들을 지움
3. 2의 배수는 전부 지워졌으니 다음 수로 넘어감
4. 다음 수(3)를 현재 소수로 선택한 후, 자신의 모든 배수를 지움
5. 구하고자 하는 max범위의 제곱근까지 검사하고 난 뒤 지워지지 않고 남은 수가 소수

이러한 흐름이다.

편리하고 쉬운 이해를 위해 짧은 영상을 첨부하겠다.(출처 - 위키백과 - 에라토스테네스의 체)

결론 : 소수를 구할 때 에라토스테네스의 체 원리를 잘 알고 있다면 훨씬 수월하게 문제를 풀 수 있다.

---

✔️ 정답 코드

#include <iostream>
#include <vector>

using namespace std;

bool number[1001];
vector<int> input;

void setPrimeNumber();

int main(void) {
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

  setPrimeNumber();
  
  int N;
  cin >> N;
  
  for (int i=0; i<N; i++) {
    int temp;
    cin >> temp;
    input.push_back(temp);
  }

  int count=0;
  for (int i=0; i<input.size(); i++) {
    if (number[input[i]])
      count++;
  }

  cout << count;

   return 0;
}

void setPrimeNumber() {
  number[1]=false;
  for (int i=2; i<1001; i++)
    number[i]=true;

  for (int i=2; i*i<1001; i++) {
    if (number[i]) {
      for (int j=i+i; j<1001; j+=i) {
        if (number[j]) {
          number[j]=false;        
        }
      }
    }
  }
}