2

200万以下的素数之和怎么求？Project Euler 第 10 个问题，http ://projecteuler.net/problem=10 。我测试了我的代码低于 10 并且工作起来就像一个魅力。但是低于 200 万似乎不起作用：/ 已经大约 15 分钟了，而且还在继续，我认为应该不会花那么长时间，对吧？我会尝试 sum 函数，但我仍然不明白为什么这不起作用？

编辑：我想我不能使用 sum 函数，因为数字甚至没有存储在数组中：/

我的代码：

#include <iostream>

using namespace std;

int main()
{
    unsigned long long x,y,z=0,s[200000],a,sum=0;
    bool isprime;
    for(x=3;x<2000000;x++)
    {
        for(y=2;y<x;y++)
        {
            if(x%y!=0 && x!=y)
            {
                isprime =true;
            }
            else
            {
                isprime =false;
                break;
            }
        }
        if(isprime ==true)
        {
                s[z] = x;
                z++;
                isprime = false;
        }
    }
    cout<<z;
    for(a=0;a<z;a++)
    {
        sum=sum+s[a];
        cout<<"Sum is being calculated "<<sum<<"\n";
    }
    cout<<"The sum is "<<sum+2<<" LADIES";
}
4

4 回答 4

3

您的问题是您的程序将检查太多不必要的除数。

为了检查给定整数是否为素数，您需要检查它是否没有小于或等于其平方根的除数。因为，如果有一个大于平方根的除数，则商将是一个整数，并且会小于平方根。

#include <iostream>

using namespace std;

int main()
{
    unsigned long long x,y,z=0,s[200000],a,sum=0;
    bool isprime;
    for(x=3;x<2000000;x++)
    {
        for(y=2; y*y <= x ;y++)
        {
            if(x%y!=0 && x!=y)
            {
                isprime =true;
            }
            else
            {
                isprime =false;
                break;
            }
        }
        if(isprime ==true)
        {
                s[z] = x;
                z++;
                isprime = false;
        }
    }
    cout<<z;
    for(a=0;a<z;a++)
    {
        sum=sum+s[a];
        cout<<"Sum is being calculated "<<sum<<"\n";
    }
    cout<<"The sum is "<<sum+2<<" LADIES";

您可以改用向量：

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    unsigned long long x,y;
    std::vector<unsigned long long> primes;
    bool isprime = true;

    for(x=3; x<2000000; x++)
    {
        isprime = true;
        for(y=2; y*y <= x ;y++)
        {
            if(x%y==0 || x==y)
            {
                isprime=false;
                break;
            }
        }
        if(isprime)
        {
            primes.push_back(x);
        }
    }
    unsigned long long sum = 2 + std::accumulate(v.begin(), v.end());
    cout<<"The sum is "<<sum<<" LADIES";
}
于 2013-04-19T14:02:36.387 回答
3

如果您使用筛子，这既简单又快速：

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

应该只需要一两秒钟即可运行。

于 2013-07-19T17:44:04.660 回答
0

当试图总结素数并包括'n'时，我想出了以下解决方案。我希望你觉得很容易理解：

function sumPrimes(num) {

  // determine if a number is prime
  function isPrime(n) {
    if (n === 2) return true;
    if (n === 3) return true;
    if (n % 2 === 0) return false;
    if (n % 3 === 0) return false;

    var  i = 5;
    var  w = 2;
    while (i * i <= n) {
        if (n % i === 0) {
            return false;
        }
        i += w;
        w = 6 - w;
    }
    return true;
  }

  // subtract 1 for 'not being prime' in my context
  var sum = isPrime(num) ? num - 1 : -1;

  for (var x = 0; x < num; x++) {
    if (isPrime(x) === true) {
      sum += x;
    }
  }

  return sum;
}
于 2016-09-14T05:07:04.603 回答
-1

使用千里马，我可以生成所有提高到幂的素数这是一个示例：

factor(product(i,i,2000000,2001000));
2^1005*3^499*5^255*7^169*11^101*13^83*17^61*19^54*23^46*29^36,,,,,2000939*2000941*2000953*2000959*2000963*2000969*2000989

然后我尝试抽象出部首并将它们加在一起。我认为如果你有足够的耐心，它可能会起作用。会很久的！！！

于 2013-07-19T12:34:13.627 回答