CODEWITHSUNDEEP
pythonprimes
Weafs.py
Weafs.py

Reputation: 23002

Consecutive Prime Sum

I am solving the 50th problem on Project Euler.

The question is to:

Find the prime number below one-million, which can be written as the sum of the most consecutive primes.

For example, 41 = 2 + 3 + 5 + 7 + 11 + 13

41 is the prime number that can be written as the sum of the most consecutive primes.

I wrote a code to find the prime numbers below 1000 that can be written as the sum of the most consecutive primes, to check if my code finds the prime number(953) which can be written as the sum of the most consecutive primes below 1000. This is what I came up with:

#!/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

Output when I run the code:

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]

The problem is it doesn't find the prime number 953 which is the longest sum of consecutice primes that adds to a prime below 1000.

So, I changed my code to troubleshoot what it does when prm is 953 in the for loop:

#!/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

Output:

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

Any idea what I am doing wrong here? Thanks for any help.

Upvotes: 2

Views: 8759

Answers (3)

Koder
Koder

Reputation: 1

This Question was asked in 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;
}

OUTPUT

Sample Output 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

Sample Output 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

Upvotes: 0

davidlowryduda
davidlowryduda

Reputation: 2559

A smaller example: if you were finding the largest sum of consecutive primes with sum less than 10, then that is 3 + 5 = 8, not 2 + 3 = 5.

It might not (and is not) the case that you always get the largest sum by adding all the primes starting at 2.

Upvotes: 2

Strikeskids
Strikeskids

Reputation: 4052

Your loop always starts with the index 2. The consecutive primes it seems don't necessarily need to start with the prime 2. You will need to vary which prime the consecutive adding starts at.

Upvotes: 3

Related Questions