blob: b5974bb4ba65b4ddeadd9c5e89071bceb479c477 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include "sieve.hh"
#include <cmath>
#include <cstring>
[[nodiscard]] std::vector<int> segmentedSieve(std::size_t size) {
const size_t s = sqrt(size);
const auto primes = sieve3(s);
std::vector<int> r{primes};
std::vector<int> r2;
size_t l = s;
size_t h = l + s;
unsigned char *n = (unsigned char *)malloc(s);
while (l < size) {
memset(n, false, s);
for (const auto prime : primes) {
// find the first number divisible by prime
std::size_t f = (l / prime) * prime;
if (f < l)
f += prime;
for (std::size_t i = f; i < h; i += prime)
n[i - l] = true;
}
for (std::size_t i = 0; i < s; ++i)
if (n[i] == false)
r2.emplace_back(i + l);
l += s;
h += s;
}
free(n);
r.reserve(r.size() + r2.size());
r.insert(r.end(), r2.begin(), r2.end());
return r;
}
|
