素因数関係の列挙

勉強

今日、「素因数の総数の列挙がエラトステネスの篩の計算量程度に抑えられている」という話題がでて、混乱したので、メモ。

問題

1〜Nまでのすべての整数に対して素因数に関するなんらかの数の列挙を行うこと。

  • 素数の列挙
  • 整数xの相異なる素因数の個数の列挙
  • 整数xの素因数で最大のものの列挙
  • 整数xの重複を含めた素因数の総数の列挙

やりかたと計算量

エラトステネスの篩の計算量はO(NloglogN)程度。


相異なる素因数の個数は、エラトステネスの篩で倍数を計算するときにインクリメントすればよい。O(NloglogN)程度。


重複を含めた素因数の総数は、最大の素因数で割っていくような計算して上げれば、再帰的・DP的に求めることができる。
再帰的に考えると、150=2*3*5^2のような場合、最大素因数は5で、これを割った値は2*3*5=30で、これの総数に+1したものだとわかる。30を最大素因数5で割った値は2*3=6で、6をの総数に+1したものだとわかる。素数の場合は総数が1であることがわかるので、求められる。
これをDP的に求めると、最大素因数を求めるO(NloglogN)+列挙O(N)程度で求められる。

コード

#define PMAX 1000000

//素数の列挙
bool isprime[PMAX+1];
void init_prime(){
  fill(isprime, isprime+PMAX+1, true); 
  isprime[0] = isprime[1] = false; 
  for(int i=2; i<=PMAX; i++) { 
    if(!isprime[i]) continue;
    for(int j=i*2; j<=PMAX; j+=i){
      isprime[j] = false; 
    }
  }
}

//整数xの相異なる素因数の個数w(x)の列挙
// w(60) = w(2^2 * 3 * 5) = 3
int pfucnt[PMAX+1];
void init_pfucnt(){
  pfucnt[0] = 0; pfucnt[1] = 1;
  for(int i=2; i<=PMAX; i++){
    if(pfucnt[i]!=0) continue;
    for(int j=i; j<=PMAX; j+=i){
      pfucnt[j]++;
    }
  }  
}

//整数xの素因数で最大のものpfmax(x)の列挙
// pfmax(60) = 5
int pfmax[PMAX+1];
void init_pfmax(){
  pfmax[0] = 0; pfmax[1] = 1;
  for(int i=2; i<=PMAX; i++){
    if(pfmax[i]!=0) continue;
    for(int j=i; j<=PMAX; j+=i){
      pfmax[j] = i;
    }
  }
}

//整数xの重複を含めた素因数の総数Ω(x)の列挙
// Ω(60) = Ω(2^2 * 3 * 5) = 4
// xが2のべき乗ならΩ(x) = log(n)/log(2)
int pfnum[PMAX+1];
void init_pfnum(){
  pfnum[0] = 0; pfnum[1] = 1;
  for(int i=2; i<=PMAX; i++){
    if(isprime[i]) pfnum[i] = 1; //isprimeじゃなくてi==pfmax[i]でよさそう
    else pfnum[i] = 1 + pfnum[i/pfmax[i]];
  }
}

その他

すべての整数に対して試し割り(O(sqrtN))すると、O(Nsqrt(N))になってしまうので、N=10^6あたりですでに怪しいが、上記なら、余裕で間に合う。


http://sucrose.hatenablog.com/entry/2014/10/10/235805
ちなみに、計算量的には、線形でのエラトステネスの篩があるよう(定数倍きついっぽい)なので、素因数関係の列挙はO(N)でできるっぽい。