3

所以我正在尝试项目欧拉的问题50。（如此接近 2 级：D）它是这样的：

素数 41 可以写成六个连续素数之和： 

41 = 2 + 3 + 5 + 7 + 11 + 13

这是添加到低于 100 的素数的最长的连续素数之和。与素数相加的一千以下的最长连续素数之和包含 21 项，等于 953。哪一个小于一百万的素数可以写为最多连续素数之和？

这是我的代码：

#include <iostream>
#include <vector>
using namespace std;

int main(){
    vector<int> primes(1000000,true);
    primes[0]=false;
    primes[1]=false;
    for (int n=4;n<1000000;n+=2)
        primes[n]=false;
    for (int n=3;n<1000000;n+=2){
        if (primes[n]==true){
            for (int b=n*2;b<100000;b+=n)
                primes[b]=false;
        }
    }
    int basicmax,basiccount=1,currentcount,biggermax,biggercount=1,sum=0,basicstart,basicend,biggerstart,biggerend;
    int limit=1000000;
        for (int start=2;start<limit;start++){
            //cout<<start;
            sum=0;
            currentcount=0;
            for (int basic=start;start<limit&&sum+basic<limit;basic++){
                if (primes[basic]==true){
                    //cout<<basic<<endl;
                    sum+=basic;currentcount++;}
                    if (primes[sum]&&currentcount>basiccount&&sum<limit)
                        {basicmax=sum;basiccount=currentcount;basicstart=start;basicend=basic;}

            }
            if (basiccount>biggercount)
                {biggercount=basiccount;biggermax=basicmax;biggerend=basicend;biggerstart=basicstart;}
        }
    cout<<biggercount<<endl<<biggermax<<endl;
    return 0;
}

基本上，它只是创建一个包含最多 1000000 的所有素数的向量，然后循环遍历它们以找到正确的答案。答案是 997651，计数应该是 543，但我的程序分别输出 997661 和 546。可能有什么问题？

4

2 回答 2

2

看起来您正在构建错误的素数向量

        for (int b=n*2;b<100000;b+=n)
            primes[b]=false;

我认为应该是 1,000,000 而不是 100,000。最好将该数字重构为常数，以确保它始终保持一致。

其余的看起来基本没问题，虽然没有自己测试，我不确定我们还能添加什么。有很大的提高效率的空间：您确实对范围进行了很多重复扫描，例如当为假时没有必要开始求和prime[start]，您可以为求和等构建仅素数的第二个向量。（Euler 项目是否有运行时和内存限制限制？我不记得了）

于 2012-04-18T16:21:55.203 回答
0

你正在以错误的方式思考这个问题。

  1. 生成最大的素数序列，使得它们的总和小于 1,000,000。这是 2, 3, 5, ..., p。对于一些 p。
  2. 对这个序列求和并测试它的素数。
  3. 如果它是素数，则终止并返回总和。
  4. 较短的序列必须是正确的。缩短序列和保留连续素数属性的方法有两种——删除第一个元素或删除最后一个元素。使用这两个序列从 2 递归。
于 2012-04-18T16:29:01.587 回答