来自Eratosthenes优化筛网的两个数字之和的总和

这里是我写的代码，它对我来说是给了我n和m之间的素数总和。来自Eratosthenes优化筛网的两个数字之和的总和

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

现在，我试图通过只是把在实践中通常是什么奇数进一步优化筛。这里是我写

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链接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

所以我应该再包括这些案件之间找到它分开处理？，我的方法是做012,i,primeSum()的方法是否正确？或者我能以更好的方式完成它？这里有什么其他可能的索引方法？

来源

2015-05-29 Ankur Anand

也许更适合http://codereview.stackexchange.com/ – reto

@reto确定移动它自己:) –

您可能想在此删除它。 – maaartinus

你为什么不环路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; 
}

来源

2015-05-29 08:43:58 dejvuth

来自Eratosthenes优化筛网的两个数字之和的总和

回答

相关问题