N보다 작은 모든 소수 리스트: 빠른 알고리즘 Prime less than N: fast algorithm

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 배열 $\text{1 byte}\times n/3$, primes 벡터 $\text{4 byte}\times n/\log n$ 이므로 $\therefore\ 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
}