数论篇1——素数问题
素数的判定
试除法
（1）普通
复杂度：$O(n)$
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。bool prime(int x){//判断x是不是质数，是返回true，不是返回false if(x <= 1) return false; for(int i = 2; i < x; i ++){ if(x % i == 0) return false; } return true; }
（2）改进
复杂度：$O(\sqrt{n})$
bool prime(int x){ if(x <= 1) return false; for(int i = 2; i <= sqrt(x); i ++){ if(x % i == 0) return false; } return true; } //用乘法可以避免根号的误差 bool prime(int x){ if(x <= 1) return false; for(int i = 2; i * i <= x; i ++){ if(x % i == 0) return false; } return true; }
根据题目不同，有可能你需要先预处理出 $1\sim N$这$N$个数是否是素数，就是俗称的打表，再用上面的这些方法，复杂度就是$O(\sqrt{n})$，如果$N$特别大，就比较慢了。
埃式筛
原理：质数的倍数都不是质数
比如$2$是质数，那么$4,6,8,10,12...$都不是质数
然后看$3$是质数，那么$6,9,12,15,18,21...$都不是质数
然后看$4$，$4$已经被$2$标记为合数了，所以跳过
然后看$5$这样一直循环下去。
时间复杂度：$O(nloglogn)$
const int N = 100000 + 5; bool P[N]; int total,prime[N];//就往大了开，反正不用的不算内存 void AiSieve() { for (int i = 2; i < N; i++) { if (!P[i]) { prime[total++] = i; for (int j = i * 2; j < N; j += i) { P[j] = true; } } } }
线性素数筛选（欧拉筛）
在埃氏筛法的思想上，这个方法可以保证每个合数都被它最小的质因数筛去，所以一个数只会经过一次。
比如$12$，既是$2$的倍数，也是$3$的倍数，在埃氏筛中，会被$2$和$3$筛选两次，而在欧拉筛中$12$只会被$6*2$筛选，而不会被$4*3$筛选。
时间复杂度为$O(n)$，其实对于埃氏筛，$loglogn$非常小，我们能碰到的问题级别，区别其实不太大（loglog(10^10) ≈ 5.2），把埃筛看成线性也无妨，毕竟好写。很大，差了好几倍。
核心思想：
红色标注的地方是整个算法的灵魂，保证每个合数被它最小的质因数筛去。
$i\ \%\ prime[j]==0$，就是如果出现 $prime[j]\ |\ i$，
那么一定有
$prime[j]\ |\ i*prime[j+1]，prime[j]\ |\ i*prime[j+2]\ ...\ prime[j]\ |\ i*prime[tot-1]$
举个例子，对着上面的来，i = 6时，（此时小于$6$的质数都被装进prime里）
$6\ \%\ 2==0$，说明$2\ |\ 6$
那么一定有
$2\ |\ 6*3$，$2\ |\ 6*5$
也就是说$18$和$30$都有最小质因数$2$，$18=9*2,\ 30=15*2$，所以跳出循环，保证每个合数被它最小的质因数筛去。
const int N = 100000 + 5; bool M[N];//prime[i]表示i是不是质数 int prime[N], tot;//p[N]用来存质数 void EulerSieve() { for (int i = 2; i < N; i++) { M[i] = true; } for (int i = 2; i < N; i++) { if (M[i]) prime[tot++] = i;//把质数存起来 for (int j = 0; j < tot && i * prime[j] < N; j++) { M[i * prime[j]] = false; if (i % prime[j] == 0) break; } } }
拓展应用
上述算法的除去打素数表，我们可以根据算法的思想做一些别的事情。
（1）埃氏筛，获取$1\sim N$数的所有素因子
const int N = 100000 + 5; vector<int> prime_factor[N]; void get_prime_factor() { for (int i = 2; i < N; i++) { if (prime_factor[i].size() == 0) {//如果i是质数 for (int j = i; j < N; j += i) { prime_factor[j].push_back(i); } } } }
（2）埃氏筛，获取1~N数的所有素因数分解
const int N = 100000 + 5; vector<int> prime_factor[N]; void factorization() { for (int i = 2; i < N; i++) { if (prime_factor[i].size() == 0) {//如果i是质数 for (int j = i; j < N; j += i) { int temp = j; while (temp >= i) { if (temp % i == 0) { prime_factor[j].push_back(i); temp /= i; } else break; } } } } }
Miller - Rabin素数测试
本段落参考：http://www.matrix67.com/blog/archives/234
费马小定理：
若$p$是质数，且$gcd(a,p) = 1$，那么$a^{p-1}mod\ p=1$
根据逆反命题的等价性，不满足$2^{(n-1)} mod\ n = 1$的$n$一定不是素数；如果满足的话则多半是素数。那么如果我只计算$2^{(n-1)} mod\ n$的值，那么素性判断出错的概率有多少？在前10亿个自然数中共有50847534个素数，而满足$2^{(n-1)} mod\ n = 1$的合数n有5597个。这样算下来，算法出错的可能性约为0.00011。这个概率太高了，我们刚才只考虑了$a=2$的情况。对于式子$a^{(n-1)} mod\ n$，取不同的a可能导致不同的结果。一个合数可能在$a=2$时通过了测试，但$a=3$时的计算结果却排除了素数的可能。于是，人们扩展了伪素数的定义，称满足$a^{(n-1)} mod\ n = 1$的合数n叫做以a为底的伪素数。前10亿个自然数中同时以2和3为底的伪素数只有1272个，这个数目不到刚才的$\frac{1}{4}$。这告诉我们如果同时验证$a=2$和$a=3$两种情况，算法出错的概率降到了0.000025。容易想到，选择用来测试的a越多，算法越准确。通常我们的做法是，随机选择若干个小于待测数的正整数作为底数a进行若干次测试，只要有一次没有通过测试就可以判定不是素数。这就是费马素性测试。
但是居然就有这样的合数，假设为n，它可以通过所有a（小于n，且满足$(gcd,n)=1$的数）的测试（这个说法不准确，详见我在地核楼层的回复）。而且第一个这样极端的伪素数小得惊人，仅仅是一个三位数，561。前10亿个自然数中这样的数有600多个。
Miller和Rabin两个人的工作让Fermat素性测试迈出了革命性的一步，建立了传说中的Miller-Rabin素性测试算法。新的测试基于下面的定理：
二次探测定理：
若$p$为质数，$x^{2}\equiv 1(mod\ )p$，则有$x\equiv (mod\ p)$或$x\equiv p-1(mod\ p)$
算法描述：
Miller-Rabin素性测试同样是不确定算法，我们把可以通过以a为底的Miller-Rabin测试的合数称作以a为底的强伪素数。第一个以2为底的强伪素数为2047。第一个以2和3为底的强伪素数则大到1 373 653。对于大数的素性判断，目前Miller-Rabin算法应用最广泛。一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就有一些技巧了。比如，如果被测数小于4 759 123 141，那么只需要测试三个底数2, 7和61就足够了。当然，你测试的越多，正确的范围肯定也越大。如果你每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试，所有不超过341 550 071 728 320的数都是正确的。如果选用2, 3, 7, 61和24251作为底数，那么$10^16$内唯一的强伪素数为46 856 248 255 981。这样的一些结论使得Miller-Rabin算法在OI中非常实用。通常认为，Miller-Rabin素性测试的正确率可以令人接受，随机选取k个底数进行测试算法的失误率大概为$4^{-k}$。
完整代码：
#include <iostream> #include <math.h> #include <time.h> using namespace std; int prime[5] = { 2, 3, 7, 61,24251 }; long long quickPower(long long down, long long e, long long mod) { long long a = down, res = 1; while (e) { if (e & 1) res = ((res % mod) * (a % mod)) % mod; a = ((a % mod) * (a % mod)) % mod; e >>= 1; } return res; } bool MillerRabin(long long p) { if (p == 1 || p == 0)return false; for (int i = 0; i < 5; i++) { if (p == prime[i])return true; if (p % prime[i] == 0 || p < prime[i])return false; int a = i, e = p - 1; if (p % prime[i] == 0 || e & 1)return false; while (!(e & 1)) { int res = quickPower(a, e, p); if (res == 1) e /= 2; else if (res == p - 1) return true; else return false; } } return true; } int main() { long long N; while (cin >> N) { if (MillerRabin(N)) { cout << "Y" << endl; } else cout << "N" << endl; } }
素数的一些神奇性质
（1）所有大于$2$的素数都可以唯一地表示成两个平方数之差。
证明如下：
（2）麦森数
如果$2^{p}-1$是素数，其中指数$p$一定也是素数。
证明如下：
原命题的逆否命题为：如果$p$不是素数，则$2^{p}-1$不是素数。
如果p不是素数，可以假设 $p=m\cdot n$
$2^p-1=(2^m)^{n}-1=(x-1)(x^{n-1}+x^{n-2}+...+1), x=2^m$
逆否命题成立，原命题成立。
拓展：
求$2^{p}-1$的位数，$2^{p}-1$和$2^{p}$的位数是相同的，因为$2^{p}$最后一个一定不为$0$，可以直接求$2^{p}$的位数。设$k=2^{p}$，根据$10^n$的位数为$n+1$，只要想办法把$k=2^{p}$中的底数$2$转换成$10$，指数$+1$就是位数了。根据$10^{log_{10}{2}}=2$，于是$k=(10^{log_{10}{2}})^p$，把$p$乘进去就是$k=10^{p\cdot log_{10}{2}}$，所以位数就是$p\cdot log_{10}{2}+1$（cmath中自带log10()函数）
（3）当$n$为大于$2$的整数时，$2^{n}+1$和$2^{n}-1$两个数中，如果其中一个数是素数，那么另一个数一定是合数。
证明如下：
$2^n$一定不能被$3$整除
如果$ (2 ^ {n} \% 3 == 1)$，则一定有：$2 ^{ n} - 1 \% 3 == 0$；
如果 $(2 ^ {n} \% 3 == 2)$，则一定有：$2 ^{ n} + 1 \% 3 == 0$;
也就是说，$2^{n}+1$和$2^{n}-1$中至少有一个是合数。
（4）大于$3$的素数一定是$6$的倍数$ ±1 $
证明如下：
素数$±1$必然是偶数，一定可以被2整除
素数除以$3$，如果余$1$，减$1$后余$0$,；如果余$2$，加$1$后余$0$，即可以素数$±1$后被$3$整除
结合上面两行，素数$±1$，一定可以被$6$整除
