使用递归方法识别素数[java]

Question

问题如下。 main() 通过调用 isPrime() 检查数字 1-10。我认为我的数学是正确的，但是除 2 之外的每个数字都不是素数。

我已经检查了一些关于SO的解决方案和问题，但是，我似乎无法达到相同的结果。

原来的问题：

public class PrimeChecker {
// Returns 0 if value is not prime, 1 if value is prime
   public static int isPrime(int testVal, int divVal) {
      // Base case 1: 0 and 1 are not prime, testVal is not prime

      // Base case 2: testVal only divisible by 1, testVal is prime

      // Recursive Case
         // Check if testVal can be evenly divided by divVal
         // Hint: use the % operator

         // If not, recursive call to isPrime with testVal and (divVal - 1)
      return 0;
   }

   public static void main(String[] args) {
      int primeCheckVal = 0; // Value checked for prime

      // Check primes for values 1 to 10
      for (primeCheckVal = 1; primeCheckVal <= 10; ++primeCheckVal) {
         if (isPrime(primeCheckVal, (primeCheckVal - 1)) == 1) {
            System.out.println(primeCheckVal + " is prime.");
         }
         else {
            System.out.println(primeCheckVal + " is not prime.");
         }
      }
   }
}

到目前为止我的解决方案：

     public class PrimeChecker {
     // Returns 0 if value is not prime, 1 if value is prime
   public static int isPrime(int testVal, int divVal) {
      int resultVal = 0;

      if ((testVal == 0) || (testVal == 1)){
         resultVal = 0;
      }// Base case 1: 0 and 1 are not prime, testVal is not prime

      else if (divVal == 1) {
         resultVal = 1;
      }// Base case 2: testVal only divisible by 1, testVal is prime

      else {
         if((testVal % divVal != 0) && (testVal / divVal == 1)) {
            isPrime(testVal, (divVal-1));
         }
         else {            
             resultVal = 1;

      }
      }
      return resultVal;
       }

      public static void main(String[] args) {
      int primeCheckVal = 0; // Value checked for prime

      // Check primes for values 1 to 10
      for (primeCheckVal = 1; primeCheckVal <= 10; ++primeCheckVal) {
        if (isPrime(primeCheckVal, (primeCheckVal - 1)) == 1) {
            System.out.println(primeCheckVal + " is prime.");
         }
         else {
            System.out.println(primeCheckVal + " is not prime.");
         }
      }
   }
}

Answer 1

更改 if/else 块

     if((testVal % divVal != 0) && (testVal / divVal == 1)) {
        isPrime(testVal, (divVal-1));
     }
     else {            
         resultVal = 1;

  }

到

if (testVal % divVal != 0) {
  return isPrime(testVal, (divVal-1));
} else {            
  resultVal = 0;
}

基本上，您忘记了返回递归结果，因此代码继续返回错误的内容。如果

testVal % divVal == 0

，则该数字不是素数，因此您返回零。另外，不要使用仅取零或一值的整数；使用

boolean

。

Answer 2

根据你的问题，我认为下面的代码会更容易。

public class PrimeChecker {
// Returns 0 if value is not prime, 1 if value is prime
   public static int isPrime(int testVal, int divVal) {
      // Base case 1: 0 and 1 are not prime, testVal is not prime
      if (testVal <= 1) {
         return 0;
      }
        
      // Base case 2: testVal only divisible by 1, testVal is prime
      if (divVal == 1) {
         return 1;
      }
        
      // Recursive Case
      // Check if testVal can be evenly divided by divVal
      // Hint: use the % operator
      if (testVal % divVal == 0) {
         return 0;
      }
      // If not, recursive call to isPrime with testVal and (divVal - 1)
      return isPrime(testVal, divVal - 1);
   }

   public static void main(String[] args) {
      int primeCheckVal;     // Value checked for prime

      // Check primes for values 1 to 10
      for (primeCheckVal = 1; primeCheckVal <= 10; ++primeCheckVal) {
         if (isPrime(primeCheckVal, (primeCheckVal - 1)) == 1) {
            System.out.println(primeCheckVal + " is prime.");
         }
         else {
            System.out.println(primeCheckVal + " is not prime.");
         }
      }
   }
}

Answer 3

这是我如何使用递归解决它

// Returns 0 if value is not prime, 1 if value is prime   

public class RecursionPrimeChecker {

   public static int isPrime(int testVal, int divVal) {
  // Base case 1: 0 and 1 are not prime, testVal is not prime
   if(testVal == 0 || testVal == 1) {
       return 0;
   }

  // Base case 2: testVal only divisible by 1, testVal is prime
   else if(divVal == 1) {
       return 1;           
   }
  // Recursive Case
   else {
       // Check if testVal can be evenly divided by divVal
       // Hint: use the % operator
       if(testVal % divVal == 0) {
           return 0;
       }           
       // If not, recursive call to isPrime with testVal and (divVal - 1)
       else {
           return isPrime(testVal, divVal-1);
       }
   }

}

public static void main(String[] args) {
      int primeCheckVal;  

      // Check primes for values 1 to 20
      for (primeCheckVal = 1; primeCheckVal <= 20; ++primeCheckVal) {
         if (isPrime(primeCheckVal, (primeCheckVal - 1)) == 1) {
            System.out.print(primeCheckVal + " ");
         }
      }
   }

}

// output
// 2 3 5 7 11 13 17 19