All pastes #2092415 Raw Edit

Something

public text v1 · immutable
#2092415 ·published 2011-10-22 04:22 UTC
rendered paste body
vector<int> primes(14642);

void seive()
{
	int i = 5;

	vector<int> candidates(160907, 1);
	
	candidates[0] = 0;
	candidates[1] = 0;
	candidates[2] = 1;
	candidates[3] = 1;

	int currentPrime = 5;

	while(currentPrime < 450)
	{
		while(!candidates[currentPrime] && !(currentPrime%2 == 0 || currentPrime%3==0)) ++currentPrime;

		for(int i = currentPrime * currentPrime; i < 160907-1; i += currentPrime)
		{
			candidates[i] = 0;
		}

		++currentPrime;
	}

	int index = 0;
	int prime = 0;

	while(index < 14642)
	{
		while(!candidates[prime]  || prime%2 == 0 || prime%3==0) ++prime;
		primes[index] = prime;
		++index;
		++prime;
	}

}