通过使用阿特金的筛计算低于2万股普赖姆数之和 [英] Calculating sum of prime number below 2 million by using Sieve of Atkin
问题描述
我在做项目欧拉，我得到了这个问题。我运行code在VS 2013和程序崩溃，因为溢出。
I'm doing project Euler and I got this problem. I run the code in VS 2013 and the program crashes because of overflow.
这是我的方法：
void problem10()
{
long long int iter = 2, sum = 0;
//Sieve of Atkin
bool isPrime[PRIME_LIMIT+1];
for (long long int i = 5; i <= PRIME_LIMIT; i++)
{
isPrime[i] = false;
}
long long int lim = ceil(sqrt(PRIME_LIMIT));
for (long long int x = 1; x <= lim; x++)
{
for (long long int y = 1; y <= lim; y++)
{
long long int n = 4 * x*x + y*y;
if (n <= PRIME_LIMIT && (n % 12 == 1 || n % 12 == 5))
{
isPrime[n] = true;
}
n = 3 * x*x + y*y;
if (n <= PRIME_LIMIT && (n % 12 == 7))
{
isPrime[n] = true;
}
n = 3 * x*x - y*y;
if (x > y && n < PRIME_LIMIT && n % 12 == 11)
{
isPrime[n] = true;
}
}
}
// eliminate composites by seiving
for (long long int n = 5; n <= lim; n++)
{
if (isPrime[n])
{
for (long long int k = n*n; k <= PRIME_LIMIT; k+= k*k)
{
isPrime[k] = false;
}
}
}
for (long long int n = 5; n <= PRIME_LIMIT; n++)
{
if (isPrime[n])
{
sum += n;
}
}
sum = sum + 2 + 3;
printf("%lld\n", sum);
/* //A basic approach -- too slow
while (iter < PRIME_LIMIT)
{
bool isDivisible = false;
int prime = iter;
for (int a = 2; a < iter; a++)
{
if (prime%a == 0)
{
isDivisible = true;
break;
}
}
if (isDivisible){}
else
{
//printf("prime is: %d\n", prime);
sum += prime;
}
iter++;
}
printf("Sum of prime is: %d\n", sum);
*/
}
该方法包括2的方法来计算所有质数的范围 PRIME_LIMIT 的总和。第二种方法需要很长时间才能得到结果，而且可能需要整整一天。第一种方法是使用阿特金的筛，程序崩溃！
This method includes 2 approaches to calculate the sum of all prime numbers in ranges PRIME_LIMIT. The second approach take too long to get the result, and probably take whole day. The first approach is using sieve of Atkin, the program crashes!
有没有在我的code任何错误？请帮助！
Is there any mistake in my code?? Please help!
推荐答案
那么，让我们来谈谈这个问题：
So, let's talk about this problem:
就像Java的，在C整数有一个限制，他们可以容纳的大小。在这里，你选择使用得到long long int 。幸运的是，对于这个问题，总和将适合该数据类型。对于其他项目欧拉的问题，则需要使用BIGINT类。
Much like Java, Integers in C have a limit to the size that they can fit. Here, you chose to use a long long int. Luckily for this problem, the sum will fit in that data type. For other Project Euler problems, you will need to use a BigInt class.
如果你添加一个另外的缓慢方式实际上是罚款。我们知道，我们需要搜索除数的列表，实际上是比所有号码从少 2，...，N 。因此，我们可以改变你的循环中的一个是：
The slow approach is actually fine if you add one addition. We know, that the list of divisors that we need to search, is actually less than all of the numbers from 2 ... n. So we can change one of your loops to this:
int max = ciel(sqrt(iter));
for (int a = 2; a < max; a++)
if (prime % a == 0)
isDivisible = true;
break;
如果我们这样做，你的code将完成比较快。
If we do that, your code will finish relatively quickly.
我还没有完全通过这个code消失了，因为它看起来并不像我记得埃拉托色尼的筛子，但最起码，你要溢出你分配堆栈。
I haven't fully gone through this code, because it doesn't look like the sieve of eratosthenes that I remember, but at the very least, you are going to overflow the stack with your allocations.
#define PRIME_LIMIT 2000000
bool isPrime[PRIME_LIMIT+1];
让我们来解决这个问题：
Let's fix that:
#define PRIME_LIMIT 2000000
static bool isPrime[PRIME_LIMIT+1]
或者
#define PRIME_LIMIT 2000000
bool *isPrime = calloc(PRIME_LIMIT + 1, sizeof(bool));
推荐
我真的建议不要试图实现阿特金的筛开始。如果我是执行这是一个学习的过程，我会做的顺序是：
Recommendations
I'd really recommend to not start by trying to implement the Sieve of Atkin. If I was to implement this as a learning exercise, I'd do it in this order:
-
这是你之前所做的那样慢的方法。在Python中，类似code，约需要1分钟的时间解决问题。我怀疑把C做它在大约10秒（或更快）。
The slow approach that you've done above. In python, similar code takes about 1 minute to solve the problem. I'd suspect C could do it in about 10 seconds (or faster).
埃拉托色尼的筛是一个更简单的实现筛。我建议你使用，明年。
The sieve of eratosthenes is a much simpler sieve to implement. I'd recommend using that next.
然后尝试实施的阿特金的筛。这个速度的算法是这个尺寸虽然有问题完全不必要的。
Then try to implement the sieve of atkin. An algorithm of that speed is completely unnecessary for a problem of this size though.
这篇关于通过使用阿特金的筛计算低于2万股普赖姆数之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
