CODEWITHSUNDEEP
c++
cortex
cortex

Reputation: 699

Output wrong Project Euler 50

So I am attempting Problem 50 of project euler. (So close to level 2 :D) It goes like this:

The prime 41, can be written as the sum of six consecutive primes: 

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

This is the longest sum of consecutive primes that adds to a prime below one-hundred. The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953. Which prime, below one-million, can be written as the sum of the most consecutive primes?

Here is my code:

#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;
}

Basically it just creates a vector of all primes up to 1000000 and then loops through them finding the right answer. The answer is 997651 and the count is supposed to be 543 but my program outputs 997661 and 546 respectively. What might be wrong?

Upvotes: 3

Views: 1091

Answers (2)

satnhak
satnhak

Reputation: 9861

You are thinking about this the wrong way.

  1. Generate the maximal sequence of primes such that their sum is less than 1,000,000. This is 2, 3, 5, ..., p. For some p.
  2. Sum this sequence and test it for primality.
  3. If it is prime terminate and return the sum.
  4. A shorter sequence must be the correct one. There are exactly two ways of shortening the sequence and preserving the consecutive prime property - removing the first element or removing the last. Recurse from 2 with both of these sequences.

Upvotes: 0

Rup
Rup

Reputation: 34408

It looks like you're building your primes vector wrong

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

I think that should be 1,000,000 not 100,000. It might be better to refactor that number out as a constant to make sure it's consistent throughout.

The rest of it looks basically fine, although without testing it ourselves I'm not sure what else we can add. There's plenty of room for efficiency improvements: you do do a lot of repeated scanning of ranges e.g. there's no point starting to sum when prime[start] is false, you could build a second vector of just the primes for the summing etc. (Does project Euler have runtime and memory limit restrictions? I can't remember)

Upvotes: 2

Related Questions