素因数分解

素因数分解はO(N^(1/2))を要する。
O(NloglogN)の前準備さえあれば、
それ以降は1からNまでの素因数分解をO(logN)で行う方法もある。

//重複を許す場合 vector 版、許さない場合 set 版を使う

// vector 版
vector<long long> p_decom(long long m){
  vector<long long> v;

  while(m % 2 == 0){
    v.push_back(2LL);
    m /= 2LL;
  }

  for(long long i = 3LL; i * i <= m; i += 2LL){
    while(m % i == 0){
      v.push_back(i);
      m /= i;
    }
  }

  if(m > 1LL){
    v.push_back(m);
  }

  sort(all(v));

  return v;
}

// set 版
vector<long long> p_decom(long long m){
  vector<long long> v;
  set<long long> se;

  while(m % 2LL == 0){
    se.insert(2LL);
    m /= 2LL;
  }

  for(long long i = 3LL; i * i <= m; i += 2LL){
    while(m % i == 0LL){
      se.insert(i);
      m /= i;
    }
  }

  if(m > 1LL){
    se.insert(m);
  }

  set<long long>::iterator itr = se.begin();

  while(itr != se.end()){
    v.pb(*itr);
    itr++;
  }

  sort(all(v));

  return v;
}

// O(logN)版

#define N 100000

long long prime[N+1];

// 下準備
void init_prime(long long n){
  memset(prime,0,sizeof(prime));
  for(long long i = 2; i < n+1; i++){
    if(prime[i] == 0){
      for(long long j = i*2; j < n+1; j += i){
        prime[j] = i;
      }
    }
  }
}

// 先にinit_primeしておくこと
vector<long long> p_decom(long long a){
  vector<long long> ret;
  while(prime[a]!=0){
    ret.pb(prime[a]);
    a /= prime[a];
  }
  ret.pb(a);
  sort(ret.begin(),ret.end());
  return ret;
}