判断一个数是质数最快的方法？为什么？
不明白。为什么，望指教
/**
n>=3 and n is odd.
*/
int isPrime(int n)
{
int k, upperBound=n/2;
for(k=3; k<=upperBound; k+=2)
{
upperBound=n/k;
if(n%k==0)
return 0;
}
return 1;
}
[解决办法]
假设n=A*B 则只需要测试不大于min(A,B)的数就能找到n的一个因子,每次加2而不会漏掉因子二是因为假设
n=2*A(则经过有限次后k会到达A),能找到n的一个因子A,同样不会误判n为素数
[解决办法]
upperBound=n/k;
假设2~k都已经测试过不是n的因子,但n是合数,设n=A*B,则 B=n/A < n/k (K<A)
因此如果n是合数,则它的一个因子一定落在[0 n/k]内
[解决办法]
换言之，一个数N，你为了判断它是否为质数，就开始试除3、5、7...但是，如果当除以（N^1/2取整，记为m）这个数的时候还没有能够除尽，那么就没有继续下去的必要了。因为假设N存在一个比m大的因数k，那么N/k是小于m的，这跟上述条件（N除以3、5、7...m都不能除尽）产生了矛盾
[解决办法]
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
最小的素数是2， 他也是唯一的偶素数。 最前面的素数依次排列为：2，3，5，7，11，13，17，...... 不是质数且大于1的正整数称为合数。 质数表上的质数请见素数表。 依据定义得公式： 设A=n2+b=(n-x)(n+y),除n-x=1以外无正整数。故有： y=（b+nx)/(n-x) (x<N-1)无正整数，则A为素数。 因为x<N-1,而且N-X必为奇数，所以计算量比常规少很多。 详见互动百科素数分布和不定方程 100以内的质数（素数）：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 （共25个）
[解决办法]
算术基本定理
算术基本定理： 任何大于1的正整数n可以唯一表示成有限个素数的乘积: n=p_1p_2...p_s, 这里p_1p_2 ...p_s是素数。 这一表达式也称为n的标准分解式。 算术基本定理是初等数论中最基本的定理。由此定理， 我们可以重新定义两个整数的最大公因子和最小公倍数等等概念。 1不能称作素数，是因为要确保算术基本定理所要求的唯一性成立。这一解释可参看华罗庚《数论导引》
[编辑本段]素数分布问题
素数分布问题，就是指素数在正整数集或其特殊子集中的分布情况，比如素数个数问题等等。这方面的结果如下; （1）欧几里得以反证法证明了素数个数无限；欧拉利用解析方法也证明了此结论。 （2）高斯提出著名的素数定理（当时是猜想，后被证明）： 设π(x)是不超过x的素数个数， 那么极限(x趋向于无穷) lim π(x)/(x/Ln x)=1 更好的逼近公式有高斯提出的li(x)函数， 即lim π(x)/lix=1。 其中 （3） 狄利克雷 证明了任何等差数列： a, a+d,a+2d,...a+nd,... (这里a,d互质)中都包含无限个素数。 （4） 兰伯特猜想（已被证明）： 在n和2n之间必定存在一个素数， 这里n是大于1的正整数。
[解决办法]
说快的话，LZ给的方法不算太快，当n很大的时候，效率比较低。
一般常用的是米勒-罗宾，log(n)^2应该可以搞定，前几年，印度的科学家给出了一种测试方法，
是确定的并且时间复杂度为常数，不过常数比较大，大概10^8左右，在实际应用当中，一般比不上米勒-罗宾。
[解决办法]
[解决办法]
[解决办法]
唔。引用错数字了。刚才那个是测试到17的时候的最小反例。只测试到13的话最小反例是3,474,749,660,383。比maxint32要大多了，比maxint64要小多了。
[解决办法]
其实就是米勒罗宾，估计FancyMouse同志给出的这个数，应该是这几个都能测过的（2-17），否则用不着这么大，能通过测试的合数多了。不过具体怎么找到这么大的数的，就不清楚了。估计Int64范围的话，还得多测几个。
[解决办法]
其实这个问题很复杂
AR素性检查,比上面提到的方法都快,都缺点是不能给出其因子,若判断一个数是素数,该方法所能给出的全部信息就是:此数不是素数,仅此而已
[解决办法]
AR素数检测是什么？可否详细讲一下。
[解决办法]
我也不了解AR检测是什么，不过楼上的回复其实是有些不严谨的，比如不能给出其因子，如果是素数就不存在什么因子，另外这个检测相信也不是一个确定性的检测，大概跟Rabin-Miller类似，复杂度上也不可能低于log(n)。