백준 1978번 소수 찾기 (C++)

solvd.ac 티어 : 브론즈2

문제 유형 : 수학, 정수론, 소수 판정 

문제 배경 지식

- 제곱근 최적화 (Square root optimization)

 어떤 자연수 x가 소수인지 판별하려면 2부터 x-1까지의 수를 나눠서 확인할 수 있다. 그러나, 이는 O(n)으로 비효율적이다.

더 효율적인 방법이 제곱근 최적화이다. 제곱근 최적화는 확인할 필요없이 2부터 sqrt(x)까지만 나눠서 확인하면 충분하다는 알고리즘이다. 시간 복잡도는 O(sqrt(n))으로 위의 방법보다 효율적이다.

- 간단한 증명

문제 해결 소감 : 소수 판별 알고리즘을 학습할 수 있어서 기쁘다

문제 해결 전략 : 1은 따로 처리해주어야 하고 이외에는 제곱근 최적화 알고리즘 을 그대로 구현했다.

#include <cmath>
#include <iostream>
#include <vector>
int n;
int temp;
int ans;
std::vector<int> v;
int main(void) {
  std::cin >> n;
  ans = n;
  for (int i = 0; i < n; i++) {
    std::cin >> temp;
    v.push_back(temp);
  }
  for (int num : v) {
    if (num == 1) {
      ans -= 1;
      continue;
    }
    int sqrt = static_cast<int>(std::sqrt(num));
    for (int i = 2; i <= sqrt; i++) {
      if (num % i == 0) {
        ans -= 1;
        break;
      }
    }
  }
  std::cout << ans;
}