如何检查 10 位数字是否为质数？

Question

我知道 Sieve 的算法，并且直到现在我一直在使用它来获得高达 10 亿的素数。

但现在我需要知道一个 10 位数字是否为质数，而 Sieve 的算法无法在限定时间内计算出它。

我搜索了很多，发现了 Fermat 的素数测试，但它没有成功，因为有些部分我无法理解，而另一部分告诉它只能通过一些迭代来判断它是否可能是素数。

我想知道如何在 1 秒左右的时间内测试这么大的数是否为质数？什么是最有效的 solution/algorithm？

编辑我还添加了我的 Sieve 算法代码。

public class Random18 {

    public static int sieveOfEratosthenes(int n) 
    { 
        // Create a boolean array "prime[0..n]" and initialize 
        // all entries it as true. A value in prime[i] will 
        // finally be false if i is Not a prime, else true. 
        boolean primes[] = new boolean[n+1]; 
        Arrays.fill(primes,true);        // assume all integers are prime.

        primes[0]=primes[1]=false;       // we know 0 and 1 are not prime.
        for (int i=2;i<primes.length;i++) {
            //if the number is prime, 
            //then go through all its multiples and make their values false.
            if(primes[i]) {
                for (int j=2;i*j<primes.length;j++) {
                    primes[i*j]=false;
                }
            }
        }
        if(primes[n]==true)
            return 1;

        else
            return 0;
    } 


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter");

        int p = scanner.nextInt();

        long t1 = System.currentTimeMillis();

        int k = sieveOfEratosthenes(p);

        long t2 = System.currentTimeMillis();

        if(k==1)
            System.out.println("yes");

        else
            System.out.println("no");

        System.out.println("took "+(t2-t1)+" millis");


        scanner.close();
    }

}

Output for big numbers like this:
999999937
yes
took 24363 mills

Answer 1

此方法跳过所有偶数，只尝试数字的平方根。对于您给定的号码

，它工作正常

public class Prime {
    public static void main(String[] args) {
        isPrime(999999937L);
    }

    public static boolean isPrime(long num) {
        if (num > 2 && num % 2 == 0) {
            System.out.println(num + " is not prime");
            return false;
        }
        int top = (int) Math.sqrt(num) + 1;
        for (int i = 3; i < top; i += 2) {
            if (num % i == 0) {
                System.out.println(num + " is not prime");
                return false;
            }
        }
        System.out.println(num + " is prime");
        return true;
    }
}

我从here

那里拿走了它

Answer 2

您可以检查它是否是质数：

public class Prime {

public static void main(String[] args) {

    int num = 10;
    boolean flag = false;
    for(int i = 2, max = num/2; i <= max; ++i)
    {
        // condition for nonprime number
        if(num % i == 0)
        {
            flag = true;
            break;
        }
    }

    if (!flag)
        System.out.println(num + " is a prime number.");
    else
        System.out.println(num + " is not a prime number.");
}}

Answer 3

public static void main(String[] args) {
    try (Scanner scan = new Scanner(System.in)) {
        System.out.print("Enter: ");
        long val = scan.nextLong();
        long t1 = System.currentTimeMillis();
        System.out.println(isPrime.test(val) ? "yes" : "no");
        System.out.println("took " + (System.currentTimeMillis() - t1) + " millis");
    }
}

static final LongPredicate isPrime = val -> {
    if (val < 2)
        return false;

    for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
        if (val % i == 0)
            return false;

    return true;
};

输出：

Enter: 999999937
yes
took 1 millis

Answer 4

我总是使用这段代码来检查一个整数是否为素数

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

Answer 5

仅仅为了测试几个数字而创建筛子是低效的。十位数在这种情况下相当小，就好像它是非质数一样，它必须有一个介于 2 和 sqrt(9_999_999_999) 之间的除数。所以你检查它是否偶数，然后有 50k 个候选除数要检查。

如果不想自己做，JDK里直接有BigInteger.valueOf(x).isProbablePrime(certainty)。 Guava 中还有 LongMath.isPrime(long x)。

如何检查 10 位数字是否为质数？

How to check if a 10 digit number is prime or not?

java

performance

primes