使用递归方法确定用户输入的质数

Question

我需要用Java创建一个程序来确定一个数是否为素数。

用户应输入任意数字，程序将确定它是否为素数，并显示“不是素数”或“素数”。我的代码现在编译并运行，但它总是说一个数字不是总理，即使它是。

import java.util.Scanner; 

public class PrimeNumber 
{ 
public static void main(String[] args) 
    { 
    Scanner input = new Scanner(System.in); 
    int constant = 0; 
    int variable = 0; 
    System.out.println("Enter a Number to test if Prime or Not"); 
    constant = input.nextInt(); 
    variable = constant; 
    double answer = 0.0; 
    answer = testPrime(constant, variable); 
    System.out.println(+answer); 
    if (answer == 1) 
    { 
    System.out.println(+constant + " is a prime number."); 
    } 
    else 
    { 
    System.out.println(+constant + " is NOT a prime number."); 
    } 
    } 

public static double testPrime(int number, int divide) 
{ 
    double prime = 0.0; 
    prime = number%divide; 
    if (prime > 0 && divide != number) 
    { 
    return testPrime(number, divide - 1); 
    } 
    else 
    { 
    return prime; 
    } 
} 
} 

Answer 1

if (prime > 0 && divide != number) 

这不会是真的。因为你的分水岭和数字总是相等的。

看到已分配variable=constant，这就是你传递给方法

constant = input.nextInt(); 
variable = constant; 
answer = testPrime(constant, variable); 

这就是说，你需要走这么复杂，以找出是否一个数是质不是什么。检查网络的简单算法。例如，请参阅http://www.mkyong.com/java/how-to-determine-a-prime-number-in-java/。

Answer 2

不是OP想要递归的答案（我想是功课）。

你只需要去，直到n的平方根，看它是否有一个除数（除数除自会<的sqrt（n））的

boolean isPrime(int n) { 
      if(n % 2 == 0)return false; 
      int till = (int)java.lang.Math.pow(n, 0.5); //(int)n/2; 
      for(int i= 3;i<till;i+=2) { 
       if(n % i == 0) 
        return false; 
      } 
      return true; 
     } 

Answer 3

我看你要为这个递归如此，我将tgkprog的答案转换为递归方法（尽管他的效率肯定更高）。另外，如果输入不是素数，我认为你可能想要返回一个素数因子？我只是猜测这从OP的返回值而不是布尔值来判断。尽管如此我会返回一个int，因为返回double是愚蠢的。

int isPrime(int n){ //starter function 
     if(n<=1) return n; //sanity check for weird inputs 
     if(n % 2 == 0) return 2; //2 is a prime factor 
     int start = (int)java.lang.Math.pow(n, 0.5); 
     return isPrime(n,start-(start%2)); //makes start odd if it wasn't already 
} 

int isPrime(int n, int testval){ //recursive function 
     if(testval<=1) return 1; //n is prime, return n since it has no prime factors 
     if(n % i == 0) 
      return i; //found a prime factor! 
     return isPrime(n,i-2); 
} 

Answer 4

递归

import java.util.Scanner; 

public class PrimeRecursion 
{ 
    static int dbg; 
    public static void main(String[] args) 
    { 
     Scanner input = new Scanner(System.in); 
     System.out.println("Enter non 0 if you want debug :"); 
     dbg = input.nextInt(); 
     long constant = 3; 
     long variable = 0; 
     while(true){ 
      System.out.println("Enter a Number to test if Prime or Not (1 to exit)"); 
      constant = input.nextLong(); 
      if(constant < 3){ 
       if(constant == 2){ 
        System.out.println("2 is a special prime"); 
       } 
       return; 
      } 
      if(constant % 2 == 0){ 
       System.out.println(constant + " is NOT a prime number, even number."); 
      }else{ 
       variable = (long)Math.pow(constant, 0.5); 
       variable = (variable % 2 == 1) ? variable : variable + 1;//odd number 
       double answer = 0.0; 
       answer = testPrime(constant, variable); 
       System.out.println("End answer : " + answer); 
       if (answer == 1){ 
        System.out.println(+constant + " is a prime number. answer : " + answer); 
       } 
       else{ 
        System.out.println(constant + " is NOT a prime number.answer : " + answer); 
       } 
      } 
      System.out.println(); 
     } 
    } 

    static double testPrime(long number, long divide) 
    { 
     double prime = 0.0; 
     prime = (double)number/divide; 
     if(dbg > 0){ 
      System.out.println("Debug number " + number + " | divide " + divide + " |prime : " + prime + " | Math.abs(prime) " + Math.abs(prime)); 
     } 
     if (prime == ((long)prime))//whats the best way to do this? 
     { 
      //divided evenly 
      return divide; 
     } 
     else{ 
      return testPrime(number, divide - 2); 
     } 
    } 
} 

Answer 5

我的递归函数是这样，纠正我，如果我wrong.Thank you.calling声明>布尔B = isPrime（数字，1列） ; 递归功能 -

void isPrime(int p,int d); 
{ 
int prime=p%d; 
if((p==0&&d>1)||p%2==0) 
return true;//that the number is not prime 
if(d==1) 
return false; 
else 
return isPrime(p,d-2);//calls the function again 
} 

Answer 6

好吧，我直接给你所有的代码，而不是编写代码段。希望大家都喜欢这个，因为我尽可能地让自己尽可能简单。 的代码是：>

import java.util.*; 
class Prime_Number 
{ 
    static int c=0; 
    public static void main(String args[]) 
    { 
     int n,i,sq=0; 
     Scanner in=new Scanner(System.in); 
     Prime_Number ob=new Prime_Number(); 
     System.out.print("Enter a no.:>"); 
     n=in.nextInt(); 
     i=n; 
     sq=(int)(Math.sqrt(n));//square root is been taken since a no. cannot have factors greater than its square root 
     int k=ob.prime_Chk(n,i,sq); 
      if(k==1) 
       { 
       System.out.println("Prime"); 
       } 
       else 
        { 
         System.out.println("Non-Prime"); 
         } 
     } 
public int prime_Chk(int g,int i,int sq) 
    { 
     if(i==sq) 
     { 
      return c; 
     } 
     else 
     { 
      if(g%i==0) 
      { 
       c++; 
      } 
      i--; 
      return(prime_Chk(g,i,sq)); 
     } 
    } 
} 

那么在黄金（）我已经采取INT I，诠释平方和INT G作为那些arguments.Instead如果你愿意，那么你可以采取其他变量也。

Answer 7

import java.util.Scanner; 

public class HW8R_T03 { 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 

     Scanner sc = new Scanner(System.in); 
     System.out.print("Enter number: "); 
     int n = sc.nextInt(); 
     int simple = prime(n,n-1); 
     System.out.println(simple==1 ? "prime" : "not prime"); 

    } 

    static int prime(int x, int y){ 
     int div = 1; 
     if (y==0 || y==1){ 
      return div; 
     } 
     if (x%y==0){ 
      div = y; 
     } else { 
      div = prime (x, --y); 
     } 
     return div; 
    } 


}