This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/number-theory/enumerate-primes.hpp"
エラトステネスの篩を用いて素数を列挙します。
vector< int > enumerate_primes(int n)
$n$ 以下の素数を昇順に返します。
#include "prime-table.hpp"
vector< int > enumerate_primes(int n) {
if(n <= 1) return {};
auto d = prime_table(n);
vector< int > primes;
primes.reserve(count(begin(d), end(d), true));
for(int i = 0; i < d.size(); i++) {
if(d[i]) primes.push_back(i);
}
return primes;
}
#line 1 "math/number-theory/prime-table.hpp"
/**
* @brief Prime Table(素数テーブル)
* @docs docs/prime-table.md
*/
vector< bool > prime_table(int n) {
vector< bool > prime(n + 1, true);
if(n >= 0) prime[0] = false;
if(n >= 1) prime[1] = false;
for(int i = 2; i * i <= n; i++) {
if(!prime[i]) continue;
for(int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
return prime;
}
#line 2 "math/number-theory/enumerate-primes.hpp"
vector< int > enumerate_primes(int n) {
if(n <= 1) return {};
auto d = prime_table(n);
vector< int > primes;
primes.reserve(count(begin(d), end(d), true));
for(int i = 0; i < d.size(); i++) {
if(d[i]) primes.push_back(i);
}
return primes;
}