在java中,验证超过12位的素数的有效算法是什么?

ni65a41a  于 2021-07-13  发布在  Java
关注(0)|答案(1)|浏览(303)

关闭。这个问题需要细节或清晰。它目前不接受答案。
**想改进这个问题吗?**通过编辑这个帖子来添加细节并澄清问题。

四年前关门了。
改进这个问题
如何在java中实现一个有效的代码来验证一个给定的数字对于大于或等于12位的数字是否是素数?
例子

Input:
100123456789
Output: prime
Input:
101111111111
Output: prime
Input:
101740496633
Output: prime
Input:
111111111111
Output:not prime
Input:
157639024808
Output: not prime

我试着实现下面的算法来确定它是否是素数。但对于大于或等于12位的数字来说,这并不需要太长时间。
我的代码

public static Boolean checkPrime(long a){
    if(a%2==0)
        return false;
    for(int i=3;i<(int)Math.sqrt(a);i=i+2){
        if(a%i==0){
            return false;
        }
    }
    return true;    
}

“a”是要检查的数字
如果给定的数字是素数,则上述函数返回true;如果给定的数字不是素数,则返回false。
对于大于12的数,如何确定给定的数是否为素数?

pokxtpni

pokxtpni1#

通过只检查值的1/3而不是1/2,可以稍微加快速度。

public static boolean checkPrime(long a) {
    if (a % 2 == 0)
        return a == 2;
    for (int i = 3; i <= (int) Math.sqrt(a); i = i + 2) {
        if (a % i == 0) {
            return false;
        }
    }
    return true;
}

public static boolean checkPrime2(long a) {
    if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0) {
        return a <= 3 || a == 5;
    }
    for (int i = 6, max = (int) Math.sqrt(a); i <= max; i = i + 6) {
        if (a % (i + 1) == 0 | a % (i + 5) == 0) {
            return false;
        }
    }
    return true;
}

public static void time(String desc, BooleanSupplier run) {
    long start = System.nanoTime();
    boolean result = run.getAsBoolean();
    if (!result)
        throw new AssertionError();
    long time = System.nanoTime() - start;
    System.out.printf("%s took %.3f mill-seconds%n", desc, time / 1e6);
}

public static void main(String... args) {
    for (int i = 2; i < 1000; i++) {
        boolean a = checkPrime(i);
        boolean b = checkPrime2(i);
        if (a != b)
            throw new AssertionError(i);
    }

    for (int i = 0; i < 3; i++) {
        time("checkPrime", () -> checkPrime(9999999998987L));
        time("checkPrime2", () -> checkPrime2(9999999998987L));
    }
}

印刷品

checkPrime took 26.887 mill-seconds
checkPrime2 took 13.878 mill-seconds
checkPrime took 25.527 mill-seconds
checkPrime2 took 11.286 mill-seconds
checkPrime took 16.799 mill-seconds
checkPrime2 took 9.929 mill-seconds

这已经开始变得足够小了,不清楚多个线程是否有帮助。

相关问题