算法查找素用最少量的计算

本文介绍了算法查找素用最少量的计算的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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.

X 小于9：返回（X放大器; 1）= 0 || x == 2

X 超过约200小（可修改）：使用审判庭（你使用的是什么）

X 比1373653更小：用米勒拉宾与基地2和3

X 小于4759123141（即一切）：。用米勒拉宾与基地2,7和61

x smaller than 9: Return (x & 1) != 0 || x == 2

x smaller than about 200 (tweakable): use trial division (what you used)

x smaller than 1373653: use Miller Rabin with bases 2 and 3.

x smaller than 4759123141 (that is everything else): use Miller Rabin with bases 2, 7 and 61.