素数相关问题及算法
试除法
根据素数的定义,对于自然数\(n\),只要能够找到除了1和它本身以外,能够整除该数的正整数,那么它就不是素数。
1 | bool isPrime(int n) { |
又因为,如果\(d\)是\(n\)的约数,那么\(n=d \times n/d\),故\(n/d\)也是,且\(\min{d, n/d} \leq \sqrt{n}\),
因此只需要测试到\(\sqrt{n}\)即可。
1 | bool isPrime(int n) { |
上述方法需要约\(2^{n/2}/((n/2)\ln 2)\)次测试。
埃氏筛
对于单个小整数,试除法尚可,但是如果要枚举\(n\)以内的素数,使用试除法就需要对\(n\)以内的所有自然数都做测试,效率太低。
埃拉托斯特尼筛法,简称埃氏筛,从2开始,将每个素数的所有倍数标记为合数,如果这个\(n\)小于最后一个标出的素数的平方,那么所有小于\(n\)且未标记的都是素数。
1 | vector<bool> isPrime(n, true); |
埃氏筛的时间复杂度为\(O(n\log n \log n)\),但这个方法最大的问题在于,需要的内存随着\(n\)的增大而增大。
整数分解
试除法
分解整数,普通方法是用短除法,从最小的素数除起,知道结果为素数为止。
1 | for (int i = 2; i * i <= n; ++i) { |
既然是从最小的素数除起,上述代码在每次++i
后,为什么不检测i
是否为素数?
原因是,内层循环相当于已经把当前i
的所有倍数去除了,类似埃氏筛,故下次取到的能够整除\(n\)的i
是素数。