Java 使用用户输入检查质数

Question

我刚开始为大学编码，我必须编写一个程序来检查用户输入（整数）是否为质数。

我取得了不错的成绩，但我想征求您的意见以及我是否忘记了什么。

package uebung_3;


import java.util.Scanner;

public class PrimZahlen {

    public static void main(String[] args) {

        System.out.print("Enter a number: ");
        Scanner key = new Scanner(System.in);
        int in = key.nextInt();

        prim(in);
    }

    private static void prim(int in) {//int in is a Scanner var.
        if (in == 2 || in == 3) {

            System.out.println(in + " is a prime number");
        } else if (in == 5 || in == 7) {
            System.out.println(in + " is a prime number");
        } else if (in % 2 == 0 || in % 3 == 0) {
            System.out.println(in + " is not a prime number.");
        } else if (in % 5 == 0 || in % 7 == 0) {
            System.out.println(in + " is not a prime number.");
        } else {
            System.out.println(in + " is a prime number.");
        }
    }

}

Answer 1

您的程序不正确。这是正确的实现，现在检查从负无穷大到无穷大的所有整数，将 1 视为非素数：

public boolean isPrime(int number) {
        if(number < 2) return false;
        for(int i = 2; i <= Math.sqrt(number); i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }

Answer 2

您应该检查该数字是否只有 2 个除数（1 和他自己）。

例如：

static boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

可以优化迭代范围（从 2 到 i^2<=n）

Answer 3

你可以用更数学的方式来做，而不是只检查直到质因数 7。这是我的解决方案：

public static void main(final String[] args) {
    System.out.print("Enter a number: ");
    final Scanner key = new Scanner(System.in);
    final int in = key.nextInt();

    if (isPrime(in)) {
        System.out.println(in + " is a prime number");
    } else {
        System.out.println(in + " is not a prime number");
    }
}

private static boolean isPrime(final int in) {
    if (in < 2) return false;

    for (int i=2; i <= Math.sqrt(in); i++){
        if (in%i == 0){
            return false;
        }
    }
    return true;
}

Answer 4

最大的问题是你没有检查大于 7 的质因数；这意味着您将开始得到 n >= 121.

的错误答案

正因为其他人基本上都提出了相同的算法，所以这里有另一个实现起来很简单的算法：Sieve of Eratosthenes:

boolean isPrime(int n) {
  if (n <= 0) return false;

  // sieve is basically a boolean[], where each element will
  // contain "true" if the number is prime, "false" otherwise.
  BitSet sieve = new BitSet(n + 1);
  sieve.set(0, n + 1);

  // Zero isn't prime, nor is 1.
  sieve.clear(0); sieve.clear(1);

  for (int i = 2; i <= n; ++i) {
    if (sieve.get(i)) {
      // i is a prime number.
      // Mark all multiples of i as non-prime.
      for (int j = 2 * i; j <= n; j += i) {
        sieve.clear(j);
      }
    }
  }

  // n is prime if the corresponding element in the sieve is "true".
  return sieve.get(n);
}

请注意，您可以通过这样一种方式考虑这一点，即您可以重复使用 sieve BitSet 多次调用该方法（具体来说，您可以再次使用它以获得更小的值 n).

Answer 5

质数只有 2 个约数，即 1 和数本身。因此，要检查一个数是否为质数，您必须检查该数的所有可能的除数。例如：

boolean isPrimeNumber(int num){
    if(num < 2)
        return false;
    for(int i = 2; i <= Math.sqrt(num); i++){
        if(num % i == 0){
            return false;
        }
    }
    return true;
}

Answer 6

primality test 上的维基百科条目提供了比目前介绍的更好的测试算法，我们可以在 Java 中像

一样简单地实现它

private static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    } else if (n <= 3) {
        return true;
    } else if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    int sq = (int) Math.ceil(Math.sqrt(n));
    for (int i = 5; i <= sq; i += 6) {
        if (n % i == 0 || n % 2 + i == 0) {
            return false;
        }
    }
    return true;
}

并改变你的main方法来使用它，比如

// prim(in);
if (isPrime(in)) {
    System.out.printf("%d is prime.%n", in);
} else {
    System.out.printf("%d is not prime.%n", in);
}

Java 使用用户输入检查质数

Java Prime Number check with User Input

java

controls

numbers

input