怎么判断一个较大的数是素数还是合数,比如1234567,1002003,等等.有固定的算法么?
參考答案:这个在计算数论中是一个重要的分支，叫“素性测试”或“素性判断”。虽然人们想了许多方法，但都没有特别快的。
实际应用中的产生素数的算法往往是先有误差地判别一个数是否为素数，即伪素数，然后详细验证。
有许多专书介绍这些算法（产生素数和素性测试），如Number Theory for Computing,2nd Edition，Song Y.Yan。
但无论如何，目前素性测试的基本思想还是试除，十分低效，这令人很无奈。
在网上见到一个可行的算法（伪代码表示，其中gcd是求最大公因子）。据说是“最快”，不知确否，聊为参考。算法如下：
Input: integer n>1
1. if (nis of the form a^b ,b>1) output COMPOSITE;
2. r=2;
3. while (r<n) {
4. if (gcd(n,r)≠1) output COMPOSITE;
5. if (r is prime)
6. let q be the largest prime factor of r-1;
7. if (q>=4√rLOGn) and ( n*(r-1)/q (NOT≡) 1 (mod r) )
8. break;
9. r←r+1;
10. }
11. for a=1 to 2√rLOGn
12. if ((x-a)^n (NOT≡) (x^n-a) (mod (x^r-1),n)) output COMPOSITE;
13. output PRIME;
