连续素数和

2 投票

3 回答

8675 浏览

数据工程师

提问于 2025-04-20 03:07

我正在解决 Project Euler 上的第50个问题。

这个问题是：

找出一个小于一百万的质数，它可以表示为最多连续质数的和。

举个例子，41 = 2 + 3 + 5 + 7 + 11 + 13

41 是可以表示为最多连续质数和的质数。

我写了一段代码，目的是找出小于 1000 的质数，这些质数可以表示为最多连续质数的和。我想检查我的代码是否能找到小于 1000 的质数 953，它是可以表示为最多连续质数和的质数。以下是我写的代码：

#!/usr/bin/python

import prime

p = prime.genprimes(1000)
prms = [i for i in p]

for prm in prms:
    count = 0
    p = prm
    temp = []
    for a in prms:
        p -= a
        temp.append(a)
        count += 1
        if p == 0:
            print prm, '\t', count, '\t', temp

prime.py:

#!/usr/bin/python

def genprimes(limit):
    """
    Returns the prime numbers(generator) until the limit(inclusive) given.
    """

    D = {}
    q = 2

    while q <= limit:
        if q not in D:
            yield q
            D[q * 2] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1

当我运行代码时的输出结果：

2       1       [2]
5       2       [2, 3]
17      4       [2, 3, 5, 7]
41      6       [2, 3, 5, 7, 11, 13]    # Longest sum of consecutive primes that adds to a prime below 100
197     12      [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
281     14      [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]

问题是，它没有找到质数 953，而这个质数是小于 1000 的连续质数和中最长的。

所以，我修改了我的代码，想看看在 for 循环中当 prm 是 953 时，它的表现如何：

#!/usr/bin/python

import prime

p = prime.genprimes(1000)

prms = [i for i in p]

found = []

for prm in prms:
    if prm == 953:
        p = prm
        for a in prms:
            print p, '\t', a
            p -= a
            if p < -100:
                break

输出结果：

你们觉得我哪里做错了吗？谢谢大家的帮助。

算法优化编程挑战数学问题 Project Euler 数学编程连续素数质数和连续数列

3 个回答

这个问题是在2016年的TCS CodeVita比赛中提出来的。

#include<iostream>
using namespace std;
int main(){
        long long int num=0;
        cout<<"Enter the Size to count Prime number till NUM : ";
        cin>>num;
        long long int ary[num],j=2;
        ary[0] =2,ary[1]=3;
        for(int i=2;i<=num;i++){      // loop will add the prime number till num
                if(i%2 != 0 && i%3 != 0){
                    ary[j] = i;
                        j++;
                }
        }
        long long int k,sum=0,count=0;
        cout<<"Sum of Consecutive Prime numbers from "<<2<<" to "<<num<<endl;
        for(int i=0;i<=j;i++){
                for(k=0;k<j;k++){
                        sum+= ary[k];
                        if(sum %2 !=0 && sum%3!=0 && sum<=num){
                                count++;
                            cout<<sum<<endl;
                        }
                }
        }
        cout<<"Total Consecutive Count : "<<count<<endl;
}

输出结果

示例输出1

Enter the Size to count Prime number till NUM : 20
Sum of Consecutive Prime numbers from 2 to 20
5
17
Total Consecutive Count : 2

示例输出2

Enter the Size to count Prime number till NUM : 100
Sum of Consecutive Prime numbers from 2 to 100
5
17
41
77
Total Consecutive Count : 4

回答于 2025-04-20 由 Python大师

分享举报

举个简单的例子：如果你要找连续质数的最大和，并且这个和要小于10，那么最大的和就是 3 + 5 = 8，而不是 2 + 3 = 5。

并不是说你从2开始加所有的质数就一定能得到最大的和，这种情况并不总是成立。

回答于 2025-04-20 由 Python大师

分享举报

你的循环总是从索引2开始。看起来连续的质数不一定要从质数2开始。你需要改变一下，从哪个质数开始进行连续相加。

回答于 2025-04-20 由 Python大师

分享举报

连续素数和

3 个回答

撰写回答