java 使用递归方法通过用户输入确定素数

Determine prime number by user input using recursive method

提问by Erica LeHuray

I need to create a program in Java that determines if a number is prime.

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

The user should enter any number, and the program will determine if it's prime or not, and display "not prime" or "prime." My code now compiles and runs but it always says a number isn't prime even if it is.

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

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

回答by hop

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

This will never be true. Because your divide and number are always equal.

这永远不会是真的。因为你的除法和数字总是相等的。

See that you have assigned variable=constantand that's what you pass to the method

看到您已分配variable=constant，这就是您传递给方法的内容

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

That said, you need go so complex to find out if a number is prime or not. Check the web for simple algorithms. See http://www.mkyong.com/java/how-to-determine-a-prime-number-in-java/for example.

也就是说，您需要非常复杂才能确定一个数字是否为质数。检查网络上的简单算法。例如，参见http://www.mkyong.com/java/how-to-determine-a-prime-number-in-java/。

回答by tgkprog

Not the answer as the OP wants recursion (homework I guess).

不是 OP 想要递归的答案（我猜是作业）。

You need to only go till the square root of n to see if it has a divisor (divisor besides self will be < sqrt(n))

你只需要直到 n 的平方根，看看它是否有一个除数（除 self 之外的除数将是 < 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;
        }

回答by Suedocode

I see you want recursion for this, so I converted tgkprog's answer to a recursive method (although his is definitely more efficient). Additionally, I think you may want to return a prime factor if the input isn't prime? I'm just speculating this judging from the OP's return value of a double instead of a boolean. Mine will return an int though, because returning a double is silly.

我看到你想要递归，所以我将 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);
}

回答by tgkprog

with recursion

带递归

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

回答by itrat jameel

the recursive function for me goes like-Correct me if i am wrong.Thank you.calling statement >Boolean b=isPrime(number,number-1); recursive function-

递归函数对我来说就像 - 如果我错了，请纠正我。谢谢。调用语句 >Boolean b=isPrime(number,number-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
}

回答by adityam1305

Well I am directly giving you all the code instead of writing snippet. Hope you all may like this one as I have tried my best to make it as simple as possible. The code is :>

好吧，我直接给你所有的代码，而不是写代码片段。希望你们都喜欢这个，因为我已经尽力让它尽可能简单。代码是：>

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

Well in the prime() I have taken int i , int sq and int g as arguments.Instead of those if you wish then you can take other variables also.

好吧，在 prime() 中，我采用了 int i 、 int sq 和 int g 作为参数。如果您愿意，也可以采用其他变量。

回答by ivelina

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


}