boj 2312번 문제를 통해서 한참 잘못빠져들었던 에라토스테네스의 체의 구현 .

처음에 에라토스테네스의 체를 이용해서 소수를 먼저 100'000개의 수에 대해서 구한뒤에, 그 각각의 소수들에 대해서 문제를 해결해야겠다 싶어서 먼저 에라토스테네스의 체를 구현하고 그 수들을 활용하였다. 

처음 구현한 에라토스테네스의 체 코드는 

vector<bool> state(100'001,true);
vector<int> sieve(int n){
    vector<int> primes;
    state[1]=false;
    for(int i=2; i*i<=n;i++){
        if(!state[i]) continue;
        for(int j=i*i;j<=n; j++)
          state[j]=false;
    }
    for(int i=2;i<=n;i++)
      if(state[i]) primes.push_back(i);
    
    return primes;
}

이와 같았는데, 지속적으로 코드의 구동이 이상하고, 자꾸 결과가 이상해서 소수가 일단 제대로 카운트 된것인지 싶어서 출력해보니까 자꾸 2와 3만 나와서 에라토스테네스의 체의 구현이 잘못된것 같아서 반복적으로 읽어보고 의미를 확인해보면서 틀린 부분이 있나 찾아보았다.

 그 결과 중간에 for(int j=i*i; j<=n; j++) 형태로 코드를 작성했다는걸 확인할 수 있었다. 이때에 의미상 나에게 필요한 부분은, j가 i의 배수로써 2배, 3배,4배, ... 형태로 지속적으로 증가하는 형태가 되어야 하기 때문에 j의 변호가  j++ 형태로 1씩 증가하는게 아니라 j+=i 형태로 

i배씩 증가해야 하는데 그걸 놓친것이다. 그래서 처음에 체를 잘못걸러서 2와 3만 담겨있었던 것이다. 

 

에라토스테네스의 체를 활용하는 경우, 소수가 제대로 담겼는지 일단 먼저 확인하고 그 이후의 과정을 진행하도록 하자. 이번처럼 애초부터 체를 잘못작성해서 소수를 제대로 걸러내지 못하면 결국 원하는 답을 얻을 수 없다. 아주 많은 시간을 여기서 들였다. 다음부터는 체를 작성하고 체로 숫자를 거르고 난뒤 소수들이 제대로 걸러졌는지 확인해보도록 하자. 

 

++++++++++++++++++++++++++++++++

추가적으로, 처음 생각해낸, 에라토스테네스의 체를 이용해서 소수들을 구하고, 그 소수들을 이용해서 수를 나누어서 소인수분해를 표시할 수도 있지만, 직접 수들을 나누면서 나타내는 방법으로 소인수분해를 하고 각각의 원소들을 나타낼 수 있다.

그 방법은 애초에 11653:소인수분해 에서 사용한 방법이었고, 이 문제에서도 사용할 수 있다. 

그 방법을 같이 첨부해보자면, 

#include <bits/stdc++.h>
using namespace std;

void solve() {
  int n; cin >> n;
  for(int i = 2; i * i <= n; i++) {
    int cnt = 0;
    while(n % i == 0) {
      cnt++;
      n /= i;
    }
    if(cnt) cout << i << ' ' << cnt << '\n';
  }
  if(n != 1) cout << n << ' ' << 1 << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int t; cin >> t;
  while(t--) solve();
}

형태처럼 수들을 i=2; i*i<=n; i++ 형태의 for문을 활용해서 나누어 질때까지 나누고, 

그리고 i*i까지만 확인하기 때문에 맨 마지막에 if(n!=1) 즉 n이 1이 아니라면 그 n을 출력하면 전체 소인수들을 모두 출력하게 되는 것이다. 

소인수분해의 경우는 소수를 모두 구할 필요 없이 이러한 방법으로 출력할 수 있다는걸 알아두고 활용하도록 하자.