Как реализовать Алгоритм Решето Эратосфена от определенного числа, до данного?
Решето Эратосфена всегда начинается с 2. Его принцип - на каждом шаге находим следующее невычеркнутое число, оно является простым. Для построения массива от 900000000 до 1000000000 необходимо вычеркнуть из этого массива все кратные простым числам от 2 до 500000000, а для этого надо эти простые найти.
Раз уж я в коментариях к вопросу и так код привел (ради доказательства, что кто-то в интернете неправ), то приведу его и в качестве ответа. Код был на коленке ради быстрой проверки написан, поэтому в продакшн его так не пихайте. Глобальные переменные, константы - все это надо бы причесать.

const int BE = 900000000;
const int N = 1000000000;

std::vector<int> small_primes;

bool DivisibleBySmallPrimes(int x) {
	for (int i = 0; i < (int)small_primes.size() && small_primes[i]*small_primes[i] <= x; ++i) {
		if (x % small_primes[i] == 0) return true;
	}
	return false;
}

void ComputeSmallPrimes() {
	int n = sqrt(N);
	for (int i = 2; i <= n; ++i) {
		if (!DivisibleBySmallPrimes(i)) {
			small_primes.push_back(i);
		}
	}
}

void ComputeSieve() {
	ComputeSmallPrimes()
	std::vector<bool> sieve(N-BE+1);
	std::vector<int> primes;
	for (auto &x : small_primes) {
		int i = (BE-1) - (BE-1) % x + x;
		while (i <= N) {
			sieve[i-BE] = true;
			i += x;
		}
	}
	for (int i = BE; i <= N; ++i) {
		if(!sieve[i-BE]) {
			primes.push_back(i);
		}
	}
}

upd:
ComputeSmallPrimes можно переписать простым решетом - будет еще быстрее.