[백준] 1978번 - 소수 찾기 문제 풀이(C++)

문제

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

1978번: 소수 찾기

 

1. 문제 해석

이 문제는 소수를 찾는 문제로 주어진 N개의 수 중 소수가 몇 개인지 찾는 문제이다.

 

2. 간단한 방법

이 문제는 소수를 찾는 문제로 최적화를 하지 않고 간단하게 푸는 방법은 다음과 같다.

#include <iostream> 
using namespace std; 

int main() { 
    int n, result = 0; 
    int x, cnt = 0; 
    cin >> n; 

    for (int i = 0; i < n; i++) { 
        cin >> x; 
        for (int j = 1; j <= x; j++){ 
        	if (x%j == 0) cnt++; 
        } 

        if (cnt == 2)result++; 
        cnt = 0; 
    } 

    cout << result << '\n'; 
}

이중 반복문의 안쪽 반복문을 보면, 1에서부터 입력으로 받은 x까지 루프를 돌며 x에 대한 j의 나머지 연산자의 결과값이 0이면 cnt를 늘리고 있다. 이는 입력으로 받은 x가 소수의 정의인 '1과 자기 자신만을 약수로 가지는 수'란 것을 충족하는지 아닌지를 판단하기 위한 연산이다. 즉, cnt가 2이면 약수(어떤 수를 나누어떨어지게 하는 수)가 1과 자신밖에 없기 때문에 소수라는 것을 의미한다. 결과적으로 위 코드는 입력으로 들어온 x의 소수 판별을 수행하고 이에 대해 카운트하는 것이다. 

 

3. 최적화 방법

위 코드를 보면 소수를 판별하기 위해 1부터 자신까지 모두 확인한다는 것을 알 수 있다. 그러나, 결론부터 이야기하면 그럴 필요가 없다. 다음은 최적화 방법에 대한 설명이다.

 

16을 예로 들어보자. 16의 약수는 1, 2, 4, 8, 16이다. 이를 자세히 보면, 1 * 16, 2 * 8, 4 * 4로 묶을 수 있다는 것을 확인할 수 있다. 이때 우리는 16의 제곱근을 제외하고 모든 약수가 모두 자신을 제외한 다른 약수와 짝을 이루고 있다는 것을 알 수 있다. 즉 2부터 소수 판별이 필요한 수의 제곱근까지 확인했을 때 약수가 존재하지 않는다면 이를 소수라 할 수 있음을 의미한다. 이를 코드로 옮기면 다음과 같다. 

#include <iostream>

using namespace std;

bool check(int x){
  int cnt = 0;
  for(int i = 2; i*i <= x; i++){
    if(x%i == 0)cnt++;
  }
  
  return cnt == 0;
}

int main() {
  int n;
  cin >> n;
  
  int cnt = 0;
  int x;
  for(int i = 0; i < n; i++){
    cin >> x;
    if(x == 1)continue;
    if(check(x))cnt++;
  }
  
  cout << cnt;

  return 0;
}

4. 결론

최적화를 하지 않았을 때는 O(N)의 시간복잡도를 갖는데 최적화를 수행한다면 O(√N)의 시간복잡도를 갖게 된다.