Prime generating number finder not producing corre

问题:

I'm working on this problem:

Consider the divisors of 30: 1,2,3,5,6,10,15,30.
It can be seen that for every divisor d of 30, d+30/d is prime.

Find the sum of all positive integers n not exceeding 100 000 000 such that for every divisor d of n, d+n/d is prime.

and I thought for sure I had it, but alas, it's apparently giving me the wrong answer (12094504411074).

I am fairly sure my sieve of Eratosthenes is working (but maybe not), so I think the problem is somewhere in my algorithm. It seems to get the right answer for n = 30 (1+2+6+10+22+30 = 71 - is this correct?), but as numbers get larger, it apparently stops working.

Here is my Java code:

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);

  
   
}
}

回答1:

The maths of your sieve looks fine to me. I hacked it around to use a BitSet which is much more space efficient. Is 5761455 primes below 100,000,000 correct?

Once I got your code working I got the same figure you get (12094504411075) what figure should you be getting?

I think this bit is wrong (I have changed the variable names to match the question for clarity)

    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 I have edited this code to reflect what we finally decided was a correct solution.

Why are you breaking out of the d loop as soon as you hit a d that does not divide n? Surely that cannot be right.

However, I think you can break out of the d loop when you have a divisor that does not check.

Also, what is your intended functionality of done? It seems to have no real function.

And, why do you start sum at 3?

Removing the break I now get the value 1739023853139. Is this correct?

Added

Here's my sieve. Identical to yours but builds a BitSet which is a much more efficient structure than a HashSet in this case:

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;
}