Consecutive Integers

Im trying to solve this

Quote:

---

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?

---

I wrote this code, it should work but it doesnt !
It works correctly for number under 100, but it doesnt even work for numbers under 1000
it gives a wrong answer 281 (it must be 953)
can anyone tell me where im going wrong?

Code:

---

public class ConescutivePrimes
{
        public static boolean isPrime(int nbr)
        {
                boolean isNPrime=true;
                for (int i = 2; i < nbr; i++)
                        if ((nbr != i) && (nbr % i == 0))
                        {
                                isNPrime = false;
                                break;
                        }
                if (isNPrime == true) return true;
                else return false;
        }
        public static void main(String[] args)
        {
                int maxValue=1000,sum=0,lastPrimeSum=0;
                for (int i=2;i<maxValue;i++)
                {
                        if (isPrime(i) == true && sum+i<maxValue)
                        {
                                sum+=i;
                                if (isPrime(sum)==true)
                                        lastPrimeSum=sum;
                        }
                }
                System.out.println(lastPrimeSum);
        }
}

---

change the value of maxValue to 100 and see the correct answer,
change it to 1000 and see it go all wrong... WHY?

You assume that the consecutive primes always starts with 2 (left-boundary) with right boundary shifting... try a nested loop so you can also shift left boundary. Also you need to exit nested loop if prime numbers are no longer consecutive, or it might be better to use a nextPrime function rather than incrementing i to ensure you are iterating through consecutive prime numbers.

Yup... left boundary needs to be shifted. To get 953 you have to sum primes from 7 to 89 (note that it doesn't start at 2). Didn't do a break from loop as mentioned earlier. Had to make optimizations to allow processing of 1M within reasonable time.

Code:

---

import java.lang.*;

public class ConsecPrime
{ private int lastSum;
  private int lastCnt;
  private int lastLBnd;
  private int lastUBnd;

  public ConsecPrime(int maxval)
  { int tempSum = 0;
    int tempCnt;
    String primesCSV = "";

    lastSum = 0;
    lastCnt = 0;
    tempCnt = nextPrime(0);
    tempSum = tempCnt;
    while (tempSum <= maxval) //keep number of primes small, disregard large values
    { primesCSV = primesCSV + "," + new Integer(tempCnt).toString(); //results in string with leading comma
      tempCnt  = nextPrime(tempCnt);
      tempSum = tempSum + tempCnt;
    }
    if (primesCSV.length() == 0)
    { return;
    }
    String primes[] = primesCSV.substring(1).split(","); //substring(1) drops leading comma
    //list of primes in array minimizes iterations later
    //since calls to isPrime() and nextPrime() minimized or eliminated

   
    for (int x=0; x<primes.length; x++)
    { tempSum = 0;
      tempCnt = 0;
      for (int y=x; y<primes.length && tempSum <= maxval; y++)
      { tempSum = tempSum + new Integer(primes[y]).intValue();
        tempCnt++;
        if ((tempSum > lastSum) && (tempCnt > lastCnt) && (tempSum <= maxval))
        { if (isPrime(tempSum) ) //minimize iterations, call only when previous test successful
          { lastSum = tempSum;
            lastCnt = tempCnt;
            lastLBnd = new Integer(primes[x]).intValue();
            lastUBnd = new Integer(primes[y]).intValue();
          }
        }
      }
    }
    primes = null;
  }

  public int maxConsecPrime()
  { return lastSum;   
  }

  public int divisorCount()
  { return lastCnt;   
  }

  public int LBound()
  { return lastLBnd;   
  }

  public int UBound()
  { return lastUBnd;   
  }
 
    public static boolean isPrime(int nbr)
    { if (((nbr != 2) && (nbr % 2 == 0)) || (nbr < 2))
      { return false;   
      }

    int sqrt_nbr = new Double(Math.sqrt( new Integer(nbr).doubleValue() )).intValue() ;
    //sqrt_nbr minimizes iteration. nbr surely odd and > 2.
    for (int i=3; i <= sqrt_nbr; i=i+2) //iterate through odd numbers starting at 3
    { if (nbr % i == 0)
      { return false;
      }
    }
   
    return true;
        }

  public static int nextPrime(int nbr)
  { if (nbr < 2)
    { return 2;
    }
    else if (nbr == 2)
    { return 3;
    }
    else if (nbr % 2 == 0) //even number
    { nbr = nbr - 1; //previous odd number basis for next prime
    }

    do
    { nbr = nbr + 2; //nbr surely odd, iterate through odd numbers   
    } while ( !isPrime(nbr) );

    return nbr;
  }
}

---