Sum of primes between two number from optimized Sieve of Eratosthenes
What you did is called Sieve of Sundaram and saves half the memory. You can save factor 8 if you use a BitSet (or implement it manually e.g. using a long[]). For small numbers it costs some time, but for big numbers it may be faster when random access is involved (less memory means that more fits in cache). When dealing with really big primes, you want both optimizations.

private static boolean[] isPrime(){
    int root=(int) Math.sqrt(MAX)+1;
    int limit=(MAX-1)/2;
    boolean[] isPrime=new boolean[limit];
    Arrays.fill(isPrime, true);
    root = root/2 -1;


You really shouldn't do things like this. The problem is already confusing by the fact that you start with a number but work with an index which is half as big (and rounded down and in your case I guess additionally decremented). It's much better to use one variable for one thing.

    for(int i = 0; i &lt; root ; i++){
        if(isPrime[i]){
            for( int j = 2*i*(i+3)+3 , p = 2*i+3; j &lt; limit ; j=j+p ){


Is it correct? How do you know that you should iterate exactly up to root? Why 2*i*(i+3)+3? The first value to cross out is usually p*p, which you need to transform to index.

I wouldn't use the p = 2*i+3 formula. When compared to p = 2*i+1, you save one bit, bit it gets even more confusing.

What about something like

int numberToIndex(int oddNumber) {
    // Asserts cost nothing unless switched on.
    assert (oddNumber &amp; 1) == 1;
    // The right shift is just a faster division by 2
    return oddNumber &gt;&gt; 1;
}

int indexToNumber(int index) {
    return 2 * index + 1;
}


? By using these functions, you could make it nearly readable.

    truetruetruefalsetruetruefalsetruetruefalsetruefalsefalsetruetruefalsefalsetruefalsetruetruefalsetruefalsefalsetruefalsefalsetruetruefalsefalsetruefalsetruetruefalsefalsetruefalsetruefalsefalsetruefalsefalsefalsetruefalse


Can you read it? Do you want to read it? Maybe you should write a formatting method and get something like

3, 5, 7, -9, 11, 13, -15


where the negatives denotes non-primes (or leave them out or whatever debugging output suits you). In any case you should write a test, so that you don't have to look at the output every time you change anything. You can test some probes like

assertTrue(isPrime(127));
assertFalse(isPrime(129));


and test some small primes in loop (and get the expected value using some trivial method). Finally, you can verify that there are 105_097_565 primes which fits in int.

I wouldn't call the array isPrime as isPrime[0] must be false as 0 is no prime. So let's call it isPrimeIndex.


  Now what really bugging me is the indexing i did in primeSum() method for this optimized sieve


Sure, the 2 needs a special handling and then you should make sure that m and n are odd. I guess that you code is wrong and I'd try something like this instead:

private static int primeSum(int n, int m) {
    if (m &lt; 2) {
        return 0; // no primes below 2
    }
    if (n &lt; 2) {
       n = 2; // no primes below 2
    }
    // Add 2 if in range.
    int sum = n &lt;= 2 &amp;&amp; 2 &lt;= m ? 2 : 0;
    // Round up to next odd in a very hacky way.
    n += ~n &amp; 1;
    // Round down to next odd.
    m -= ~m &amp; 1;
    for (int i = numberToIndex(n), p = n; i&lt;=numberToIndex(m); ++i, p+=2) {
        sum += isPrimeIndex[i] ? p : 0;
    }
}


How does my hacky rounding work: If n is odd, then ~n is even and ~n &amp; 1 is 0, so nothing changes. If n is even, then ~n is odd and ~n &amp; 1 is 1, so n gets incremented. You could use something like n += (n % 2) == 0  ? 1 : 0 which is equivalent (but slower) or whatever suits you.


  So should i again include these cases and deal with it separately ? like this


My strategy is to handle special cases upfront (here: deal with the two) and normalize everything ASAP (here: ensure that m and n are odd). This tends to make things simple.