Consecutive Integers

[perito]

Im trying to solve 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?

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?

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?

[leinad31]

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.

[leinad31]

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.

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