title: Sum of Primes between two number from Optimized Sieve of Eratosthenes
body: <p>Here is the code that i wrote that is working for me to give me sum of prime numbers between <code>n</code> and <code>m</code>.</p>
  
  <pre><code>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;
  
      }
  
  }
  </code></pre>
  
  <p>Input:</p>
  
  <pre><code>2
  1 99999
  10000 99999
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>454396537
  448660141
  </code></pre>
  
  <p>Now i'm trying to <em>further optimize sieve by just taking odd number</em> what usually in practice.
  Here is the Optimized Sieve function  that i have written</p>
  
  <pre><code>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;
  }
  </code></pre>
  
  <p>Which i was able to do. I tested the above function till <code>MAX=100</code>. Here is the Ideone Link <a href="http://ideone.com/igwgF2" rel="nofollow">IDEONE LINK</a>
  Test Result</p>
  
  <pre><code>    truetruetruefalsetruetruefalsetruetruefalsetruefalsefalsetruetruefalsefalsetrue
  falsetruetruefalsetruefalsefalsetruefalsefalsetruetruefalsefalsetruefalse
  truetruefalsefalsetruefalsetruefalsefalsetruefalsefalsefalsetruefalse
  </code></pre>
  
  <p>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..</p>
  
  <p>Now what really bugging me is the indexing i did in <code>primeSum() method</code> for this optimized sieve</p>
  
  <pre><code>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;
      }
  </code></pre>
  
  <p>But as obvious this indexing of <code>n</code> is failing for <code>n&lt;3</code>. so i have to do this to get this code working </p>
  
  <pre><code>if(n&gt;0 &amp;&amp; n&lt;=2){
              sum=2;
              n=n+2;
          }
  </code></pre>
  
  <p>But then it still failing for the cases when i've to find it between ranges </p>
  
  <pre><code>1 2
  1 1
  2 2
  </code></pre>
  
  <p>So should i again include these cases and deal with it separately ?, Is my way of doing the indexing <code>i</code> in <code>primeSum()</code> method is proper ? or can i get it done in more good way ? and what are the other possible way of indexing here ?</p>