Eratosthenes - エラトステネスの篩
(lib/30-math/Eratosthenes.cpp)

• View this file on GitHub
• Last update: 2023-06-18 04:36:16+09:00

api

• Eratosthenes(int N)
  • コンストラクタ [1,N]の篩を生成

Verified with

• test/convolution/DivisorZetaMoebiusTransform-gcd-convolution.test.cpp
• test/convolution/DivisorZetaMoebiusTransform-lcm-convolution.test.cpp
• test/math/Eratosthenes.test.cpp

Code

/*
 * @title Eratosthenes - エラトステネスの篩
 * @docs md/math/Eratosthenes.md
 */
class Eratosthenes {
    unsigned int sz;
public:
    vector<unsigned int> sieve;
    vector<long long> prime;
    Eratosthenes(unsigned int N):sz(N+1),sieve(N+1, 1) {
        sieve[0]=sieve[1]=0;
        for(int i=1; i <= N/i; ++i) if(sieve[i]) for(int j=2*i;j<=N;j+=i) sieve[j]=0;
        for(int i=1; i <= N  ; ++i) if(sieve[i]) prime.push_back(i);
    }
    size_t size() const {
        return sz;
    }
};

#line 1 "lib/30-math/Eratosthenes.cpp"
/*
 * @title Eratosthenes - エラトステネスの篩
 * @docs md/math/Eratosthenes.md
 */
class Eratosthenes {
    unsigned int sz;
public:
    vector<unsigned int> sieve;
    vector<long long> prime;
    Eratosthenes(unsigned int N):sz(N+1),sieve(N+1, 1) {
        sieve[0]=sieve[1]=0;
        for(int i=1; i <= N/i; ++i) if(sieve[i]) for(int j=2*i;j<=N;j+=i) sieve[j]=0;
        for(int i=1; i <= N  ; ++i) if(sieve[i]) prime.push_back(i);
    }
    size_t size() const {
        return sz;
    }
};

Back to top page