用于找到具有最少量计算的素数的算法

Question

假设您要编写一个函数/方法来查找素数,那么最有效的方法是什么？我认为这将是一个类似这样的测试:

下面的代码在半c ++中

bool primeTest (int x) { //X is the number we're testing
    int testUpTo = (int)((sqrt(x))+1);
    for (int i=3; i<testUpTo; i+=2){
        if ((x%i)==0) {
            return false;
        }
    }
    return true;
}

有人有更好的方法去解决这个需要较少计算的事情吗？

编辑:略微改变代码,两次.我没有用任何特定的语言写这个,虽然我认为它是因为bool这个词而不是java的C++.

Answer 1

我会使用Miller Rabin测试,对于小于341,550,071,728,321(并且2 ^ 31远小于此数字)的数字,可以很容易地确定.

伪代码:有许多不同的情况.

1. x 小于9:返回 (x & 1) != 0 || x == 2
2. x 小于约200(可调整):使用试验部门(你使用的是什么)
3. x 小于1373653:使用Miller Rabin,碱基2和3.
4. x 小于4759123141(即其他一切):使用Miller Rabin,基础2,7和61.