Euler problem 50

[Vish0203]

I was trying to solve the Euler problem number 50, and wrote the following code and got the answer as,
no. of primes = 536
and prime value is 958577
But, when i search the answer for this on internet, it says 543 primes and prime is 997651
why does my program ends even if the sum is not > than 1000000 ???

#include<stdio.h>
#include<stdlib.h>
void prime();  // generates prime
int send_prime(long int);  // used to send the generated prime
int check_prime(long int); // checks whether obtained sum is prime or not
long int sum = 0;
long int p = 0;    // count of primes
int main()
{
    prime();
    return 0;
}

void prime() {
    int count = 0;
    for(long int i = 2 ; i <= 1000000 ; i++) {
        count = 0;
        for(long int j = 2 ; j <= (i/2) ; j++) {
            if(i%j == 0) {
                count++;
                break;
            }   
        }
        if(count == 0) {
            p++;    // number of prime incremented 
            int check = send_prime(i);
            if(check == 0)  // to check is sum goes beyond 1 million
                break;
        }
    }
}

int send_prime(long int x) {
    sum = sum + x;
    if(sum > 1000000)
        return 0;
    int u = check_prime(sum);
    if(u == 1 && sum < 1000000) {
        printf("\nnumber of terms = %d\n",p);
        printf("\n%d\n",sum);
        return 1;
    }
    else
        return 1;
}

int check_prime(long int x) {
    int count = 0;
    for(long int i = 2 ; i <= x/2 ; i++) {
        if(x%i == 0) {
            count++;
            break;
        }   
    }
    if(count == 0)
        return 1;
    else
        return 0;
}

[Adak]

The prime has to be less than 1,000,000, but adding up the sum must be redone for every prime - but the program doesn't reset sum to zero, when it starts working on a new prime number.

[Vish0203]

The prime has to be less than 1,000,000, but adding up the sum must be redone for every prime - but the program doesn't reset sum to zero, when it starts working on a new prime number.

why to reset? we have to calculate the sum of consecutive primes and if i reset, then the previous sum will be lost and i'll have to sum up from scratch again isn't it??

[Vish0203]

here's the exact question!

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?

[Adak]

Here's how I'd do it:

1) Use the Sieve of Erathothenes to get a list of all primes, less than 1,000,000. This is WAY faster than using trial by division or modulo. It will knock your socks off!

2) Then do your calculations to find the greatest number of consecutive primes, and their sum.

Sum has to be recalculated for each prime, because each prime has a different string of primes which, when added up, equal it.

Yes, many of the primes will have repeated primes which make it up, but ignore that. Each string of these lesser primes will sum up to it, will have some differences, that must be accounted for in sum.

[Vish0203]

Okay,
Do you have any sample C or C++ code satisfying the Seive of Erathothenes algoritm?

[Adak]

Yes, but I'm not going to rob you of the fun of discovering/verifying, what I've claimed.

This is the pseudo code:

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

 for i = 2, 3, 4, ..., not exceeding √n: (sqrt of n)
  if A[i] is true:
    for j = i2, i2+i, i2+2i, ..., not exceeding n :
      A[j] := false

Now all i such that A[i] is true are prime.

To see a graphic of it in action, and read more about it:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

At the buttom of the article, other sieves are mentioned as better/faster. Ignore them. In my testing at least, they were all slower.

Obviously, in the for loop, you want to avoid re-calculating the sqrt() of n, over and over. Calculate it one time, before the loop starts, and then save it as a variable, and use it instead.

[Vish0203]

I wrote this code! but for a value of million, it crashes! any suggestions?

#include<iostream>
#include<cmath>
#include<cstdlib>
#define MAX 1000000
using namespace std;
void sieve(int *,long int);
int main() {
    int a[MAX];
    long int n = MAX;
    //cout<<"Enter the range : ";
    //cin>>n;

    for(long int i = 2 ; i < n ; i++)
        a[i] = 1;

    sieve(a,n);
    return 0;
}

void sieve(int * a, long int n) {
    int root = sqrt(n);
    for(long int i = 2 ; i < root ; i++) {
        if(a[i] == 1) {
            for(long int j = i ; (j*i) < n ; j++) {
                a[j*i] = 0;
            }
        }
    }

    for(long int i = 2 ; i < n ; i++) {
        if(a[i] == 1)
            cout<<i<<" ";
    }
}

[Adak]

First, this is the C forum, and I don't program in C++, so code it in C, not C++.

Second, you can't create a very large array inside a function, (like you tried to do in main(). Why? Because the memory available inside any function is limited to a small portion of memory.

If you want a million int's, you will probably need to get the memory for it from the heap - that's where the BIG amount of memory is kept. You can get it by declaring your array outside and before main(), OR you can create a dynamically allocated array using malloc() or calloc() (include memory.h or stdlib.h to get the macros it needs).

One correction (my error): make the variable root +1 more. Why? Because root is an int, and sqrt() will be floating point, so root will be rounded down by one, frequently - making it short by one, otherwise.

And remember, C! (saving your file with a dot c file name extension, should do it).

[Adak]

OK, here's the test. Set your MAX for 102. Now see if you have 2 as your first prime number, and 101 as your last one. If you have that, and 26 prime numbers in total, then you're on the right track.

In the for loop you start at line #30, in your code above, I would put either all the prime numbers, or the last 1,000 prime numbers, so the highest 1,000 primes can be checked for the number of consecutive primes that go into them evenly.

I chose 1,000 of the highest primes arbitrarily - that number may need to be adjusted. Clearly, I don't expect to find the longest string of (anything), to be in the lowest bunch of primes. Larger prime numbers mean longer consecutive primes, viewed as a group. That's my thinking, anyway.

[Vish0203]

OK, here's the test. Set your MAX for 102. Now see if you have 2 as your first prime number, and 101 as your last one. If you have that, and 26 prime numbers in total, then you're on the right track.

This works fine i get first prime as 2 and last as 101 with 26 prime count

Okay, I changed the code accordingly! I added a memory allocation but when i run the code there is some unexpected crash!
And if I replace the malloc and take an array size like i did before, the code works but still the answer is not correct!
i get the answer as

for 548 primes sum is 958577

here's the code,

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define MAX 10000

void sieve(int *,long int);
void send_prime(long int);
int check_prime(long int);
int p = 0;

int main() {
    int *a;
    long int n = MAX;
    a = (int *)malloc(sizeof(int));
    for(long int i = 2 ; i < n ; i++)
        a[i] = 1;

    sieve(a,n);
    return 0;
}

void sieve(int * a, long int n) {
    int root = sqrt(n);
    for(long int i = 2 ; i < root ; i++) {
        if(a[i] == 1) {
            for(long int j = i ; (j*i) < n ; j++) {
                a[j*i] = 0;
            }
        }
    }

    for(long int i = 2 ; i < n ; i++) {
        if(a[i] == 1) {
            p++;
            send_prime(i);
        }
    }
}

//help me in this part

void send_prime(long int prime) {
    static long int sum = 0;
    long int prev;
    if(check_prime(sum)) {
        prev = sum;
    }
    sum = sum + prime;
    if(check_prime(sum) && sum > 1000000) {
        printf("for %d primes sum is %ld",p,prev);
        system("pause");
    }
}

int check_prime(long int x) {
    int root = sqrt(x);
    int count = 0;
    for(int i = 2 ; i < root ; i++) {
        if(x%i == 0)
        {
            return 0;
            count++;
            break;
        }
    }
    if(count == 0)
        return 1;
}

[Vish0203]

the check_prime() isn't correct sorry!
i'll better use the previous logic but please help me with send_prime function

[Adak]

When you were gone for a bit, I thought you'd left, and stopped thinking/working on this topic.

I'll get back to it, since you're here.

This is what I use for Sieve of Eratosthenes.

//Uses the Sieve of Eratosthenes algorithm
int getPrimes(void) {
   int root,i,j;

   a[0]=0;a[1]=0;

   root = sqrt(MAX)+1; 
   for(i=2;i<root;i++) {
      if(a[i]) {
         for(j=i*i;j<MAX;j+=i) {
            a[j]=0;
         }
      }
   }
   //print out the primes, 10 per row
   for(i=0,j=0;i<MAX;i++) {
      if(a[i]) {
         primes[j]=i;
         printf("%7d ",primes[j]);
         ++j;
      }
   }

   printf("\n\ncount: %d \n\n",j);
   return j; //j is the count
}

[Adak]

You don't need a check prime function, because you'll be checking the accuracy of the Sieve function, before you run it for Project Euler. I forget what the time requirement is for P.E., but they must have limits.

So no check prime function. Keep it for the "Home Edition", maybe. ;)

Let's talk algorithm for this. (and I've not done this problem on P.E. yet).
Just as I'm sure the longest number of <anything> in greatest prime factors, will be found in a large (not necessarily the largest though), prime, so too, I believe the largest # of prime factors must include many of the lowest primes as factors. They're the low-hanging fruit for this, if you get my meaning.

So I have a wild idea for this, but I need to tinker with it a bit. The idea being to not have to factor all the top N primes, which was my first thought on this.

Describe your algorithm. I'm not clear what it is by looking at the code (so far).

[Adak]

Ok, my idea to solve this problem - which may not be optimal of course - is to accept two hypothesis as true:

1) The answer (which prime < 1 million has the longest consecutive primes summing up to it's value), will be found in the top 100,000 or so primes. Anything below 900,000 can be ignored as the answer.

2) The primes which make up the longer consecutive primes, will be dominated by those primes which have the smaller consecutive primes, included. The smaller primes are the "low hanging fruit" in this problem.

The smallEST primes may not be included in the answer, but the smallER primes, will surely be there.

Adding up primes is VERY easy, and fast: i.e.:
2,3,5,7,11,13,17,19

can be added up for this problem as:
2 + 3 = 5
5 + 5 = 10
10 + 7 = 17
17 + 11 = 28, etc.

So all that needs to be done, is add the previous sum + the next prime, and we have the next sum of a longer consecutive string. No need to go back to the first prime, and start with it.

(And for some odd reason, this is beginning to smell like a problem easily solved with a fibonacci tree, but I'll continue with a brute force solution for now.)

Using the Sieve of Eratosthenes, we have all the primes in the blink of an eye. This is one implementations:

//Uses the Sieve of Eratosthenes algorithm
int getPrimes(void) {
   int root,i,j;

   a[0]=0;a[1]=0;

   root = sqrt(MAX)+1;      //include <math.h> for sqrt()
   for(i=2;i<root;i++) {
      if(a[i]) {
         for(j=i*i;j<MAX;j+=i) {
            a[j]=0;
         }
      }
   }
   //Show the primes that were found and
   //put them into the primes[] array
   for(i=0,j=0;i<MAX;i++) {
      if(a[i]) {
         primes[j]=i;
         printf("%7d ",primes[j]);
         ++j;
      }
   }

   printf("\n\ncount: %d \n\n",j);
   return j; //j is the count
}

Now comes the more difficult part. With all the possible primes, starting with 2, sum them up like this:

2
2+3=5
5+5=10
etc.

We don't need to keep the primes we're using, but we need the 2, 5, and 10, as we extend the number of consecutive primes we want.

We need ALL the combinations starting with 2 to N consecutive primes, then all the combinations starting with 3 to N consecutive primes, up to some reasonable limit - say 5,000 consecutive primes, for a top range of 1 million, perhaps.

I did mention this was a brute force attempt to solve it, didn't I? ;)

Then repeat with 2 to N+1, 3 to N+1, 5 to N+1, etc. What you want is every possible consecutive prime number combination, within reason.

Finally, with all these sums of the above combinations safely in an array, just go through the array, from greatest to least, and the first number you find that matches a prime (looking also from greatest to least is best), is the final answer.

This solution seems so "brute force" in nature, that I doubt if it's the best one, but it was the first one that I thought of. The "smell" of a fibonacci tree of primes being used to solve it, is something I'd have to think about.

Since I haven't solved Euler's #50, (or even tried it yet), the best answer - or even whether this answer will work within their time and memory constraints, is uncertain.