Sum of primes between two number from optimized Sieve of Eratosthenes Here is the code that I wrote to give me sum of prime numbers between n and m:

class TestClass {
    final static int MAX=1000000;
    final static boolean[] isPrime=isPrime();
    public static void main(String args[] ) throws Exception {
        BufferedReader keyboard= new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(keyboard.readLine());

        while(t&gt;0 &amp;&amp; t&lt;=100){
            String[] tempInt=keyboard.readLine().split(" ");
            int n=Integer.parseInt(tempInt[0]);
            int m=Integer.parseInt(tempInt[1]);

            int sum=primeSum(n,m);
            System.out.println(sum);
            t--;
        }
    }

private static int primeSum(int n, int m) {
        int sum=0;

        for(int i=n;i&lt;=m;i++){
            if(isPrime[i]){
                sum=sum+i;
            }
        }
        return sum;
    }

    private static boolean[] isPrime(){
        int maxFactor= (int)Math.sqrt(MAX);
        boolean[] isPrime=new boolean[MAX + 1];
        int len=isPrime.length;
        Arrays.fill(isPrime,true);
        isPrime[0]=false;
        isPrime[1]=false;
        for(int i=0;i&lt;=maxFactor;i++){
            if(isPrime[i]){
                for(int j=i+i;j&lt;len;j+=i){
                    isPrime[j]=false;
                }
            }
        }
        return isPrime;

    }

}


Input:

2
1 99999
10000 99999


Output:

454396537
448660141


Now I'm trying to further optimize sieve by just taking odd number what usually in practice. Here is the optimized sieve function  that I have written:

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;
        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 ){
                    isPrime[j]=false;
                }
            }
        }

    return isPrime;
}


Which I was able to do. I tested the above function till MAX=100. Here is the Ideone link.

Test results:

    truetruetruefalsetruetruefalsetruetruefalsetruefalsefalsetruetruefalsefalsetrue
falsetruetruefalsetruefalsefalsetruefalsefalsetruetruefalsefalsetruefalse
truetruefalsefalsetruefalsetruefalsefalsetruefalsefalsefalsetruefalse


i.e 3 5 7 9̶ 11 13 1̶5̶ 17 19 ̶2̶1̶  23 2̶5̶ ̶2̶7̶  29 31 ̶3̶3̶ ̶3̶5̶ ̶  37 3̶9̶ ̶  so on..

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

private static int primeSum(int n, int m) {
        int sum;
        if(n&gt;0 &amp;&amp; n&lt;=2){
            sum=2;
        }else
            sum=0;
        //System.out.println(sum);
        for( int i = (n-3)/2; i &lt;= (m-3)/2 ; i++){
            if(isPrime[i]){
                //System.out.println(i);
                sum=sum+2*i+3;
            }
        }
        return sum;
    }


But obviously, this indexing of n is failing for n&lt;3, so I have to do this to get this code working:

if(n&gt;0 &amp;&amp; n&lt;=2){
            sum=2;
            n=n+2;
        }


But then it still fails for the cases when I've to find it between ranges:

1 2
1 1
2 2


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

private static int primeSumInRange(int n, int m) {
        int sum;
        if(m ==1) return 0;
        if(n&lt;=2){
            sum=2;
            n=n+2;
        }else
            sum=0;
            if(m&gt;2){
        for( int i = (n-3)/2; i &lt;= (m-3)/2 ; i++){
            if(isPrime[i]){
                sum=sum+2*i+3;
            }
        } }
        return sum;
    }


Is my way of doing the indexing i in primeSum() method proper? Or can I improve it? What are the other possible way of indexing here?
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.