백준 1978 (에라토스테네스의 체)

1978번: 소수 찾기

 

핵심

• 소수찾기 관련 시간복잡도는 O(n), O(√n)처럼 다양한데, 그중에서 바로 생각이 안났던 에라토스테네스의 체 알고리즘으로 풀었다.
• 에라토스테네스의 체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

• 이건 거의 O(NloglogN)..? 인가 하여튼 빠르다.
• 이 문제를 풀면서 헷갈렸던게, 결국 에라토스테네스의 체를 이용하려면, 1000까지의 모든 수에 대한 배열을 만들어야 하니까 비효율적인거아닌가? 했다.(이게 1만이 될지 무한대가 될지 모르니까) 그래서 처음에는 에라토스테네스를 잘못 이해하고 할당 받은 수들(1, 3, 5, 7)만 배열에 넣어서 파악했는데 이건 잘못 적용한거였다.
• 하지만, 메모리크기를 손해보는만큼 시간복잡도가 선형시간에 가까울 만큼 동작이 빠르기 때문에 왠만하면 이 알고리즘을 사용해야할 것 같다.
• 그리고 배열대신 벡터를 사용했는데, 만약 4개라는 제공되는 숫자의 개수를 알려주지 않을 경우 벡터가 더 적합하다고 생각했기 때문이다.(근데.. 이미 1001개로 동적할당하면 굳이 쓸 필요가 없었을지도..)
• 만약 문제가 범위를 알려주고 그 사이에 있는 소수를 구하라고 했으면, vector의 size함수를 이용해서 현재 벡터에 있는 데이터 개수를 파악하는 것도 좋았을 것 같다.

#include <iostream>

#include <vector>

using namespace std;

void isPrime(int n)

{

   // 1000까지의 숫자에 대한 메모리 크기 할당

   vector<bool> savePrime(1001);

   int countPrime = 0;  // 소수 개수

   savePrime[1] = true; // 1은 소수가 아니므로 true처리

 

   for (int i = 2; i*i < 1001; i++)

   {

      // 해당수가 소수라면, 출력하고 해당수를 제외한 배수들을 모두 제외

      if (savePrime[i] == false)

      {

         for (int j = i * 2; j <= 1001; j += i)

         {

            savePrime[j] = true;

         }

      }

   }

   // 값 읽으면서 소수 찾기

   for (int i = 0; i < n; i++)

   {

      int num = 0;

      cin >> num;

      if(savePrime[num] == false)

         countPrime++;

   }

   cout << countPrime;

}

int main()

 {

   int N = 0;

   

   cin >> N;

   isPrime(N);

   

 }