算法查找素用最少量的计算 [英] Algorithm for finding a prime with the least amount of computations

问题描述

假设你要编写一个函数/方法找到一个素数，这将是最有效的方式做到这一点？我想，这将是一个测试，是这样的：

Assuming you were going to write a function / method to find a prime number, what would be the most efficient way to do this? I'm thinking that it would be a test that is something like this:

code以下在半C ++

Code Below in semi-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;
}

是否有人有一个更好的办法去解决这一点，将需要较少的计算？

Does someone have a better way to go about solving this that will take less computations?

编辑：改变code咯，两次。我并没有考虑任何特定的语言写这篇文章，但我想这是C ++对Java由于字布尔。

edit: Changed code slightly, twice. I didn't write this with any specific language in mind, although I suppose it's C++ over java due to the word bool.

推荐答案

我会使用米勒拉宾测试时，其可以容易地作出确定性为编号大于341,550,071,728,321小（2 ^ 31比小得多）。

I would use the Miller Rabin test, which can easily be made deterministic for numbers smaller than 341,550,071,728,321 (and 2^31 is much smaller than that).

伪code：有若干不同的情况

Pseudocode: there are a number of different cases.

1. X 小于9：返回（X放大器; 1）= 0 || x == 2
2. X 超过约200小（可修改）：使用审判庭（你使用的是什么）
3. X 比1373653更小：用米勒拉宾与基地2和3
4. X 小于4759123141（即一切）：。用米勒拉宾与基地2,7和61

1. x smaller than 9: Return (x & 1) != 0 || x == 2
2. x smaller than about 200 (tweakable): use trial division (what you used)
3. x smaller than 1373653: use Miller Rabin with bases 2 and 3.
4. x smaller than 4759123141 (that is everything else): use Miller Rabin with bases 2, 7 and 61.

这篇关于算法查找素用最少量的计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！