cpp/math/sieve-of-eratosthenes.cpp

• View this file on GitHub
• Last update: 2024-01-24 16:14:34+09:00

Required by

• cpp/geometry/two-points-distance.cpp
• cpp/math/meissel-lehhmer.cpp

Verified with

• cpp/z_test/yosupo-counting_primes.cpp
• cpp/z_test/yosupo-enumerate_primes.cpp

Code

struct SieveEratos{
  int N;
  vector<int> minp;
  vector<bool> t;
  vector<int> primes;
  map<int,int> invprimes;
  SieveEratos(){}
  SieveEratos(int n):N(n+1){
    generate();
  }
  void set(int n){
    N = n+1;
    generate();
  }
  void generate(){
    t.assign(N, true);
    t[0] = t[1] = false;
    for(int i = 2; N > i; i++){
      if(t[i]){
        primes.emplace_back(i);
        for(int j = i+i; N > j; j+=i){
          t[j] = false;
        }
      }
    } 
  }
  void generate_invprime(){
    for(size_t i = 0; primes.size() > i; i++){
      invprimes[primes[i]] = i+1;
    }

  }
  void generate_minfactor(){
    minp.assign(N, N+2);
    minp[0] = minp[1] = -1;
    for(int i = 2; N > i; i++){
      if(minp[i] == N+2){
        minp[i] = i;
        for(int j = i+i; N > j; j+=i){
          minp[j] = min(i, minp[j]);
        }
      }
    }
  }
  bool operator[](int x){return t[x] == x;}
};

#line 1 "cpp/math/sieve-of-eratosthenes.cpp"
struct SieveEratos{
  int N;
  vector<int> minp;
  vector<bool> t;
  vector<int> primes;
  map<int,int> invprimes;
  SieveEratos(){}
  SieveEratos(int n):N(n+1){
    generate();
  }
  void set(int n){
    N = n+1;
    generate();
  }
  void generate(){
    t.assign(N, true);
    t[0] = t[1] = false;
    for(int i = 2; N > i; i++){
      if(t[i]){
        primes.emplace_back(i);
        for(int j = i+i; N > j; j+=i){
          t[j] = false;
        }
      }
    } 
  }
  void generate_invprime(){
    for(size_t i = 0; primes.size() > i; i++){
      invprimes[primes[i]] = i+1;
    }

  }
  void generate_minfactor(){
    minp.assign(N, N+2);
    minp[0] = minp[1] = -1;
    for(int i = 2; N > i; i++){
      if(minp[i] == N+2){
        minp[i] = i;
        for(int j = i+i; N > j; j+=i){
          minp[j] = min(i, minp[j]);
        }
      }
    }
  }
  bool operator[](int x){return t[x] == x;}
};

Back to top page