Prime生成数字查找器不能产生正确的输出
我正在解决这个问题：
考虑30：1,2,3,5,6,10,15,30的除数。
可以看出，对于每个除数d为30，d + 30 / d是素数。找出所有正整数n的总和不超过100 000 000，这样对于n的每个除数d，d + n / d是素数。
我确信我有它，但是唉，它显然给了我错误的答案（ 12094504411074 ）。
我很确定我对Eratosthenes的筛子正在工作（但可能没有），所以我认为问题出在我的算法中。 它似乎得到正确的答案n = 30 （ 1+2+6+10+22+30 = 71 – 这是正确的吗？），但随着数字变大，它显然停止工作。
这是我的Java代码：
import java.util.HashSet; public class Generators { static HashSet hSet = new HashSet(); 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); } }
筛子的数学对我来说很好看。 我把它破解成使用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; } }
注意我已编辑此代码以反映我们最终认为是正确的解决方案。
一旦你击中一个不分割n的d ，你为什么要突破d循环？ 当然不可能是对的。
但是，我认为当你有一个不检查的除数时你可以突破d循环。
此外，您的目标function是done ？ 它似乎没有真正的function。
而且，你为什么在3开始sum ？
删除break我现在得到值1739023853139 。 它是否正确？
添加
这是我的筛子。 与您的相同，但构建一个BitSet ，在这种情况下，它比HashSet更有效：
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; }