1

I am attempting Problem 50 of project Euler.

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:

    public class consPrime
    {
        static int checker(int ar[],int num,int index) //returns no.of consecutive
        {                                              //primes for the given num  
            while(true)
        {

        int temp=num;

        for(int i=index;i>=0;i--)
        {
            temp=temp-ar[i];

            if(temp==0)
            {
                return (index-i+1);
            }               
        }           
        index--;
        if(index==0)
        return 0;           
        }
    }

    public static void main(String args[])
    {               
        int n=100000;
        int ar[]=new int[n];
        int total=0;int flag;

        for(int i=2;i<1000000;i++)   //Generates an array of primes below 1 million
        {
            flag=1;

            for(int j=2;j<=Math.sqrt(i);j++)
            {
                if(i%j==0)
                {
                    flag=0;
                    break;
                }                   
            }
            if(flag==1)
            {
                ar[total]=i;
                total++;
            }               
        }

        int m=0;
        int Big=0;

        for(int i=total;i>=0;i--) //Prints the current answer with no.of prime
        {
            m=checker(ar,ar[i],i-1);
            if(Big<=m)
            {Big=m;
                System.out.println(ar[i]+"     "+Big);
            }
        }           
    }       
}

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 990707 and 75175 respectively. What might be wrong?

3
  • 2
    Have you verified that your prime number array is correctly generated? Have you verified that your checker method works as you intend it to? This question needs to be narrowed down.
    – FThompson
    Apr 3, 2013 at 1:35
  • 1
    I'm not sure how your program can work at all. In this loop: for(int i=total;i>=0;i--) when i becomes 0 the call to checker passes -1 as index. Then in checker method this loop for(int i=index;i>=0;i--) starts with -1 and you attempt to retrieve ar[-1]. Aren't you are getting an Out Of Bounds exception at that point?
    – PM 77-1
    Apr 3, 2013 at 1:45
  • THere are no errors when i run the program...it works fine....but apparently generates the wrong answer!
    – KayEs
    Apr 3, 2013 at 2:48

2 Answers 2

2

Several big problems:

  1. Some minor problem first: learn to proper indent your code, learn to use proper naming convention. In Java, variable names uses camelCasing while type name uses PascalCasing.

  2. Lots of problems in your logics: you loop thru the prime number array, until you hit zero or until looped thru all numbers in the array. However, please be awared that, there is underflow/overflow for integer. It is possible that the "temp" keeps on deducts and become negative and become positive and so-on-and-so-forth and hit zero. However that's not the correct answer

  3. You only tried to find the consecutive numbers that ends at index - 1. For example, to check for prime number at index 10, you are finding consecutive primes from index 9 backwards. However consecutive prime sum up to your target number rarely (in fact almost never, except for 5) contains the "previous" prime number. The whole logic is simply wrong.

  4. Not to mention the incorrect parameters you passed for checker, which is mentioned by comment of user @pm-77-1

6
  • For your point 3: The index decrements in the outer LOOP. So i dont see how it matters if i start with the previous prime number as eventually all sets of consecutive prime numbers below the number will be checked!
    – KayEs
    Apr 3, 2013 at 2:52
  • it decrements but what you are doing now is, for example, for checking prime of index 10: first check index 9, then index 9, 8, then index 9,8,7 .... until you checked index 9,8,7,...1,0 or if u hit zero. That means, you are only checking consecutive numbers from previous prime backwards. However the correct consecutive primes can be from index 3-6, tell me how your logic can find this out Apr 3, 2013 at 3:18
  • i checked my program.The problem that was occuring was integer overflow/underflow (as you mentioned in POINT 2 and i was unaware of that, Thanks for informing). As for logic, i have 2 loops, inner loop tries to find the set of consecutive primes from index to any number n. If its not possible it then tries to find the set from index-1 to any number m. Eg for checking prime with index 10: first check for set 9,8,7...n ,if not satisfied, then go from 8,7,6..m and so on. Though IndexOutOFBound occurs now unfortunately!
    – KayEs
    Apr 3, 2013 at 3:36
  • For your logic, even you have an extra level of loop, it is still wrong. If my understanding is correct, it is possible that one prime can be composed of more than one consecutive sequences of prime. e.g. for prime at index 10, it may be composed of 5,6,7 or 1,2,3,4. However, you are only finding the "last" consecutive sequence, which may lead to wrong result. For IndexOutOfBound, check comment from pm-77-1. It is straight forward. Apr 3, 2013 at 6:09
  • Well yes. That is a flaw though i had thought earlier about it but i felt it was highly unlikely that such a situation will arise. Thanks for your suggestions. They were really helpful!
    – KayEs
    Apr 3, 2013 at 6:24
0

Here is another approach that takes 43 ms.

It is based on the following approach:

1) The primes <= 1000000 are generated using a sieve

2) It iterates in O(n2) through all numbers and it counts the consecutive primes. The first loop changes the first element of the sequence, the second one takes the elements starting from that position and adds them to a sum. If the sum is prime and it consists of the biggest number of primes, than it is kept in a variable.

import java.util.ArrayList;
import java.util.List;

public class P50 {

    private final static int N = 1_000_000;

    public static void main(String[] args) {
        boolean primes[] = generatePrimes(N);
        List<Integer> primeIntegers = new ArrayList<Integer>();
        for (int i = 0; i < primes.length; i++) {
            if (primes[i]) {
                primeIntegers.add(i);
            }
        }
        int count = 0;
        int sum = 0;
        int finalSum = 0;
        int finalCount = 0;
        int totalPrimes = primeIntegers.size();
        for (int start = 0; start < totalPrimes; start++) {
            sum = 0;
            count = 0;
            for (int current = start; current < totalPrimes; current++) {
                int actual = primeIntegers.get(current);
                sum += actual;
                if ( sum >= N ) {
                    break;
                }
                if ( primes[sum] ) {
                    if ( count > finalCount ) {
                        finalCount = count;
                        finalSum = sum;
                    }
                }
                count++;
            }
        }
        System.out.println(finalSum);
    }

    private static boolean[] generatePrimes(int n) {
        boolean primes[] = new boolean[n];
        for (int i = 0; i < n; i++) {
            primes[i] = true;
        }
        primes[0] = false;
        primes[1] = false;
        // i = step
        for (int i = 2; i * i < n; i++) {
            if (primes[i]) {
                for (int j = i * i; j < n; j += i) {
                    primes[j] = false;
                }
            }
        }
        return primes;
    }

}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.