首相は、私はこの問題に取り組んでいる正しい出力

Question

を生成していない番号ファインダーを生成：

は30の約数を考えてみましょう：1,2,3,5,6,10,15,30。
30の各除数dについて、d + 30/dが素数であることが分かる。

nのすべての約数dに対して、d + n/dが素数であるように、100 000 000 を超えないすべての正の整数nの合計を求める。

と私は確信していましたが、悲しいかな、それは明らかに私に間違った答えを与えています（12094504411074）。

Eratosthenesの私の篩が動作しているとは確信していますが、問題はアルゴリズムのどこかにあると思います。 n = 30（1+2+6+10+22+30 = 71 - これは正しいのですか？）の正解を得ているようですが、数字が大きくなると明らかに機能しなくなります。あなたのふるいの

import java.util.HashSet; 
public class Generators { 
static HashSet<Integer> hSet = new HashSet<Integer>(); 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int n = 100000000; 
    sieveErat(n + 1); //Fill a hashSet with prime numbers 
    System.out.println("Sieve complete"); 
    int check = 0; 

    long sum = 3; 


    for(int i = 2; i <= n; i++){ 
     int numDivisors = 0; 
     int numPrimeChecks = 0; 
     boolean done = false; 
     if(!hSet.contains(i+1)){ //i+1 must be a prime number for i to be prime generating 
      continue; 
     } 
     else{ 
      for(int j = 2; j < i/2; j++){ 
       if(i%j == 0){ 
        numDivisors++; 
       check = j + i/j; 
       if(hSet.contains(check)){ 
        done = true; 
        numPrimeChecks++; 
       } 
      }else{ 
       break; 
      }   

    } 
      if(numPrimeChecks == numDivisors && done){ 

       sum += i; 
      } 
     } 

    } 
    System.out.println(sum); 
} 

public static void sieveErat(int N){ 
boolean[] isPrime = new boolean[N + 1]; 

    for (int i = 2; i <= N; i++) { 
     isPrime[i] = true; 
     //count++; 
    } 
    // mark non-primes <= N using Sieve of Eratosthenes 

    for (int i = 2; i*i <= N; i++) { 

     // if i is prime, then mark multiples of i as nonprime 
     // suffices to consider mutiples i, i+1, ..., N/i 
     if (isPrime[i]) { 
      for (int j = i; i*j <= N; j++) { 
       isPrime[i*j] = false; 
      // count--; 
      } 
     } 

    } 


    for(int i = 2; i < isPrime.length; i++){ 
     if(isPrime[i]){ 
      hSet.add(i); 
     } 
    } 
    // System.out.println(count); 



} 
} 

Answer 1

数学は私には罰金になります。

は、ここに私のJavaコードです。私はそれをはるかにスペース効率の良いBitSetを使用するためにそれをハックしました。 5761455の素数は100,000,000未満ですか？

コードを取得したら、同じ数字が得られます（12094504411075）どのような数字ですかはになるはずですか？

私は

for(int d = 2; d < Math.sqrt(n+3); d++) { 
     if (n % d == 0) { 
     numDivisors++; 
     int check = d + n/d; 
     if (primes.get(check)) { 
      // **** What does done mean??? **** 
      //done = true; 
      numPrimeChecks++; 
     } else { 
      // **** Added! Got a divisor that did not check. No point in going on. 
      break; 
     } 
     } else { 
     // **** Why break here??? **** 
     //break; 
     } 

    } 

（私は明確にするため、質問と一致するように、変数名を変更した）このビットが間違っていると思うNB私たちは最終的に正解だったことを決めたものを反映するために、このコードを編集しました。

dを打つとすぐにdループを切り裂きますが、それはnを分けません。確かにそれは正しいとは言えません。

しかし、私はあなたが除数がチェックされていないときにdループから脱出すると思います。はです。

また、あなたの意図する機能は、doneですか？それは本当の機能を持っていないようです。

なぜ、sumは3になるのですか？

breakを削除しました。値は1739023853139です。これは正しいです？

を追加しました

は、ここに私のふるいです。あなたと同じですが、この場合ではHashSetよりもはるかに効率的な構造であるBitSet構築する：あなたが私にはスーパーも私のコードを文書化していないキャッチ表示されます

public static BitSet sieveOfEratosthenes(int n) { 
    BitSet isPrime = new BitSet(n); 

    // Iniially all numbers are prime. 
    for (int i = 2; i <= n; i++) { 
    isPrime.set(i); 
    } 

    // mark non-primes <= N using Sieve of Eratosthenes 
    for (int i = 2; i * i <= n; i++) { 

    // if i is prime, then mark multiples of i as nonprime 
    // suffices to consider mutiples i, i+1, ..., N/i 
    if (isPrime.get(i)) { 
     for (int j = i; i * j <= n; j++) { 
      isPrime.clear(i * j); 
     } 
    } 

    } 

    //System.out.println("Found " + isPrime.cardinality() + " primes"); 
    return isPrime; 
}