Сумма чисел между двумя номерами из Оптимизированного сита Eratosthenes

Question

Вот код, который я написал, который работает для меня, чтобы дать мне сумму простых чисел между n и 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>0 && t<=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<=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<=maxFactor;i++){ 
      if(isPrime[i]){ 
       for(int j=i+i;j<len;j+=i){ 
        isPrime[j]=false; 
       } 
      } 
     } 
     return isPrime; 

    } 

} 

Вход:

2 
1 99999 
10000 99999 

Выход:

454396537 
448660141 

Теперь я пытаюсь дальнейшей оптимизации решето, просто принимая нечетное число что обычно на практике. Вот функция Optimized Сито, что я написал

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 < root ; i++){ 
      if(isPrime[i]){ 
       for(int j = 2*i*(i+3)+3 , p = 2*i+3; j < limit ; j=j+p){ 
        isPrime[j]=false; 
       } 
      } 
     } 

    return isPrime; 
} 

Что я смог сделать. Я проверил вышеуказанную функцию до MAX=100. Вот Ideone Link IDEONE LINK Результат теста

truetruetruefalsetruetruefalsetruetruefalsetruefalsefalsetruetruefalsefalsetrue 
falsetruetruefalsetruefalsefalsetruefalsefalsetruetruefalsefalsetruefalse 
truetruefalsefalsetruefalsetruefalsefalsetruefalsefalsefalsetruefalse 

т.е. 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 ̶ 39 ° так далее ..

Теперь то, что действительно пристанет меня индексация я сделал в primeSum() method для этого оптимизированного сита

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

Но, как очевидно, эта индексация n терпит неудачу за n<3. так что я должен сделать это, чтобы получить этот код работает

if(n>0 && n<=2){ 
      sum=2; 
      n=n+2; 
     } 

Но тогда он еще не удается, за исключением случаев, когда я найти его между диапазонами

1 2 
1 1 
2 2 

Так я должен снова включать эти случаи и поделитесь с ним отдельно?, Является ли мой способ делать индексацию i в primeSum() метод правильный? или я могу сделать это более эффективно? и каков другой возможный способ индексации здесь?

Answer 1

Почему вы не петля для каждого нечетного числа между n и m:

private static int primeSum(int n, int m) { 
    int sum = 0; 
    if (n <= 2 && m >= 2) // need this because 2 not in isPrime 
     sum += 2; 
    if (n%2 == 0) // always start from an odd number 
     n++; 
    for (int i = n; i <= m; i += 2) { 
     int index = (i - 3)/2; 
     if (index >= 0 && isPrime[index]) { 
      sum += i; 
     } 
    } 
    return sum; 
}