連續的總理

Question

我正在解決的問題Project Euler上的50 ^th問題。

的問題是：

請看下面一百萬的素數，這可寫爲最連貫的質數的和。

例如，41 = 2 + 3 + 5 + 7 + 11 + 13

41是可以寫爲最連貫的素數之素數。

我寫了一個代碼來找到1000以下的素數，可以寫成最連續的素數之和，來檢查我的代碼是否找到素數（953），它可以寫成最大的總和連續素數低於1000。這是我想出了：

#!/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以下加上素數的連續素數的最長總和。

---

於是，我改變了我的代碼來解決它做什麼時prm在for循環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 

輸出：

953  2 
951  3 
948  5 
943  7 
936  11 
925  13 
912  17 
895  19 
876  23 
853  29 
824  31 
793  37 
756  41 
715  43 
672  47 
625  53 
572  59 
513  61 
452  67 
385  71 
314  73 
241  79 
162  83 
79  89 
-10  97 

任何想法，我做錯了這裏？謝謝你的幫助。

Answer 1

您的循環始終以索引2開始。連續的素數似乎不一定需要以素數2開始。您需要改變連續添加開始時的素數。

Answer 2

一個較小的例子：如果您發現總和小於10的連續素數的總和最大，那麼這就是3 + 5 = 8，而不是2 + 3 = 5。

它可能不是（也不是）你總是通過添加從2開始的所有素數來獲得最大的總和。

Answer 3

這個問題是問TCS CodeVita 2016

#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