Java 数学未返回预期值

Question

根据https://en.wikipedia.org/wiki/Lucas_primality_test，如果a^(n-1)不等于1modn，那么这个数就是合数。众所周知，3 是质数，而 9 不是。我的 Java 技能非常过时，我可能会忘记一些非常简单的事情。请记住，这也只是测试的开始，而不是测试的完整实施。下面的示例代码 return 对两个数字都是 false，而只有 9 应该 return false。

import java.util.Random;
import java.util.Scanner;

public class LucasTest
{
    private static int n;
    private static boolean primeResult;

    public static int randInt(int min, int max) {
        Random rand = new Random();
        int randomNum = rand.nextInt((max - min) + 1) + min;

        return randomNum;
    }

    public static boolean isPrime(int num)
    {
        int a = randInt(2, num - 1);
        int b = num - 1;
        double c = Math.pow(a,b);

        if (c != (1.0 % num)) {
            return false;
        }

        return true;
    }

    public static void main(String args[])
    {
        System.out.println("Enter an integer:");

        Scanner pNum = new Scanner(System.in);

        n = pNum.nextInt();

        primeResult = isPrime(n);

        System.out.println("Number is likely prime?: " + primeResult);
    }
}

Answer 1

问题出在你的 isPrime 方法的测试中。

改变

if (c != (1.0 % num))

到

if ((c % num) != 1.0)

你所做的是首先取 1.0 mod num，即 1，然后检查 c 是否不等于 1（除 num=1 外，它永远不会等于 1）。

我们需要做的是计算 c mod num，然后检查它是否为 1。

我使用此更改测试了您的代码，它正确地将 3、7 和 13 识别为质数，并将 9 和 15 识别为合数。

注意：该定理中有两个检查，您只实现了第一个。因此，您可能会随机 return 一个合数的真实陈述。此外，该定理指出 some a 对于给定的数字必须存在，但并不是说 every a 的条件都成立，因此即使两者都存在检查，当你测试一个随机 a 时，你可能会随机识别一个素数作为合数。

要完全实现定理，您必须实现第二个条件，然后检查区间 (1,n) 中的每个 a。如果两个条件都适用于任何给定的 a，则 return 为真（并且不必费心检查其他 a），否则 return 为假。当然，第二个条件更难实现，因为你必须找到 (n-1) 的质因数。

Answer 2

您分享的页面中的伪代码说。

输入：n > 2，待检验的奇数； k，决定测试准确度的参数

输出：如果 n 是素数则为素数，否则为合数或可能合数；确定 n−1 的质因数。

LOOP1: repeat k times:

  pick a randomly in the range [2, n − 1]

  if a^(n-1) != 1 (mod n) then return composite
  otherwise 
     LOOP2: for all prime factors q of n−1:
        if a^((n-1)/q) != 1 (mod n) 
           if we did not check this equality for all prime factors of n−1 
              then do next LOOP2
           otherwise return prime
        otherwise do next LOOP1
return possibly composite.

Java 数学未返回预期值

Java math not returning expected value

java

math

random

integer

modulo