エラトステネスの篩のまとめ

整数にもう少し馴染みたいという気持ちからまとめてみます，茶とか緑レベルくらいまで通用しそうなところまでです．

それにしてもdiff800の壁が高すぎる... 今acceptが140だけど200くらいで緑コーダーになりたいが遠そうな感じ．

ナイーブ

エラトステネスの篩の定義からは外れるが実装はほとんど同じなので一応書いておく．

候補i以降の全整数にiで割る作業を繰り返し計算量はO(n^ 2)

vector<ll> sieve(ll n) {
  vector<ll> prime(n, true);
  prime[0] = false;
  prime[1] = false;
  for(ll i = 2; i < n; i++) {
    if(prime[i]) {
      for(ll j = 2*i; j < n; j++) {
        if(j%i == 0) prime[j] = false;
      }
    }
  }
  return prime;
}

√nまでチェックする

nが約数を持つとき1つは必ず√n以下になるという性質を利用したもので計算量はO(n√n)．（nの約数のminを最大にしようとすると√n√nになることを考えると理解しやすい） a <= bとしたときabは既に走査済みなのでb*aについては調べる必要がなくなる

vector<ll> sieve(ll n) {
  vector<ll> prime(n, true);
  prime[0] = false;
  prime[1] = false;
  ll n2 = sqrt(n) + 1;
  for(ll i = 2; i < n2; i++) {
    if(prime[i]) {
      for(ll j = 2*i; j < n; j++) {
        if(j%i == 0) prime[j] = false;
      }
    }
  }
  return prime;

倍数のみを篩にかける

一般的にエラとステエネスの篩と言われるとこれを指す．

結局割り切れるのはiの倍数に限られるので無駄なチェックをはぶく．計算量はn個の要素についてそれぞれ倍数要素をチェックし， n/2+n/3+n/5...となりこれがO(nloglogn)になるらしい．

vector<ll> sieve(ll n) {
  vector<ll> prime(n, true);
  prime[0] = false;
  prime[1] = false;
  for(ll i = 2; i < n; i++) {
    if(prime[i]) {
      for(ll j = i; j < n; j+=i) { // jにiを足してiの倍数要素のみ走査
        if(j%i == 0) prime[j] = false;
      }
    }
  }
  return prime;
}