Nより小さいすべての小数点リスト:高速アルゴリズムPrime lessがNより小さい:fastアルゴリズム
std::vector<int> getPrimes(int n) {
std::vector<int> primes;
if (n < 3) return primes;
if (n < 4) {
primes.push_back(2);
return primes;
}
// Upper bound of π(x): https://arxiv.org/abs/1706.09803
int reserveCount = (int)((1.0 + 0.5 * log(2.0)) * n / log(n));
primes.reserve(reserveCount);
primes.push_back(2); primes.push_back(3);
int modulo = n % 6;
bool correction = modulo > 1;
switch (modulo) {
case 1: n--; break;
case 2: n += 4; break;
case 3: n += 3; break;
case 4: n += 2; break;
case 5: n++;
}
int sieveSize = n / 3;
bool* sieve = new bool[sieveSize];
memset(sieve, true, sizeof(bool) * sieveSize);
sieve[0] = false;
int last = ((int)sqrt(n)) / 3 + 1;
int i, k, idx, step;
for (int i = 0; i < last; ++i) {
if (sieve[i]) {
k = (3 * i + 1) | 1;
step = 2 * k;
for (idx = k * k / 3; idx < sieveSize; idx += step)
sieve[idx] = false;
for (idx = (k * k + 4 * k - 2 * k * (i & 1)) / 3;
idx < sieveSize; idx += step)
sieve[idx] = false;
}
}
for (i = 1; i < sieveSize - correction; ++i) {
if (sieve[i])
primes.push_back((3 * i + 1) | 1);
}
delete []sieve;
return primes;
}
スペースの複雑さ:sieve
アレイ1 byte×n/3\text{1 byte}\times n/31 byte×n/3primes
ベクトル4 byte×n/logn\text{4 byte}\times n/\log n4 byte×n/logn∴ O(n)\therefore\O(n)∴ O(n)a
からb
の間の少数auto primes = getPrimes(b+1);
auto begin = std::lower_bound(primes.begin(), primes.end(), a);
for (auto it = begin; it != primes.end(); ++it) {
int prime = *it;
// use prime in here
}
Reference
この問題について(Nより小さいすべての小数点リスト:高速アルゴリズムPrime lessがNより小さい:fastアルゴリズム), 我々は、より多くの情報をここで見つけました https://velog.io/@stripe2933/prime-less-than-n-fast-algorithmテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol