프로젝트 오일러 문제 10

Summation of primes

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

에라토스테네스의 체를 이용한 소거법으로 합성수를 제거 후 합산하는 방법을 사용한다. 

long long int Problem010(int number)
{
	long long int ret = 0;
	int* numArr = new int[number + 1];
	for (int i = 2; i <= number; i++)
	{
		numArr[i] = -1;
	}
	for (int i = 2; i <= number; i++)
	{
		if (numArr[i] == -1)
		{
			ret += i;
			for (int j = i * 2; j <= number; j += i)
			{
				numArr[j] = 0;
			}
		}
	}
	delete[] numArr;
	return ret;
}