sieve of eratosthenes seems slow

[rozick1]

I think this function works as a sieve but it seems quite slow. Can someone suggest how I can make it faster?

Thanks!

 std::vector <bool> primes (MAX);
	
	//set to true

	for (long long int i=0; i < MAX; i++)
		primes [i] = true;

	
	//sieve

	for (long long int i= 2; i < sqrt(MAX); i++)
	{
		if (primes[i] == false)
			continue;

		for (long long int j=2;true; j++)
		{
			long long int total = j * i;
			
			if (total < MAX)
				primes [total] = false;
	
			else
				break;
		
			
		}

	}

[Disch]

1) Construct the vector with the value you want, rather than iterating over it:

std::vector<bool> primes(MAX,true); // <- all elements will be true, no need to loop 

2) Don't call sqrt() every time you loop. Record the value outside the loop and use that value instead:

auto end = sqrt(MAX);
for(long long i = 2; i < end; ++i)

3) Increment by 'i' in your inner loop rather than multiplying each time:

for(long long j = i; j < MAX; j += i)
{
    primes[j] = false;
}

4) Turn optimizations on. (ie: do a "Release build" rather than a debug build)