0

I'm doing the Euler's Method project to find the sum of prime numbers below 2 million and I'm struggling. Here is the code I'm using. When I calculate the sum below 10 and the sum below 50 I'm getting the right value, but where I'm calculating the sum below 2 million project Euler is saying my solution is incorrect. Any ideas?

#import <Foundation/Foundation.h>

int main(int argc, const char * argv[])
{
    @autoreleasepool {

        int p = 2, d, total;
        BOOL isPrime;
        total = 0;
        NSLog(@"%i ", p);
        for ( p = 3; p < 2e6; p += 2){
            isPrime = YES;

            for ( d = 3; isPrime == YES && d < p; d += 2)
               if ( p % d == 0)
                   isPrime = NO;

            if (isPrime == YES){
                NSLog(@"%i ", p);
                        total  += p ;}
        }
        NSLog(@"total = %i", total + 2);


    }
    return 0;
}
4

2 回答 2

0

有几个错误。第一个是你溢出了。使用 long 而不是 int。第二件事只是性能提升。将 for 循环从 p < 2e6 更改为 p*p <= 2e6。这样你就排除了 2e6 平方根以上的所有数字。解决这些问题，你会很高兴。祝你好运！

于 2013-06-06T04:57:45.250 回答
0

此函数使用埃拉托色尼筛法对小于n的素数求和：

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

我会留给你用合适的数据类型翻译成Objective-C。对于n = 2000000，这应该在一两秒内运行。

于 2013-05-21T01:42:27.017 回答