一、素数的一些神奇性质
（1）所有大于2的素数都可以唯一地表示成两个平方数之差。
证明如下：
（2）麦森数
如果2p－1是素数，其中指数p一定也是素数。
证明如下：
原命题的逆否命题为：如果p不是素数，则2p-1不是素数。
如果p不是素数，可以假设 p=m·n
逆否命题成立，原命题成立。
（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整除
二、素数的判定
1.试除法
（1）普通
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）改进
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~N 这N个数是否是素数，就是俗称的打表，再用上面的这些方法，复杂度就是O(n·根号n)，如果N特别大，就太慢了。
2.埃式筛
原理：质数的倍数都不是质数
比如2是质数，那么4,6,8,10,12...都不是质数
然后看3是质数，那么6,9,12,15,18,21...都不是质数
然后看4，4已经被2标记为合数了，所以跳过
然后看5......这样一直循环下去
const int N = 100000 + 5; bool M[N]; void AiSieve() { for (int i = 2; i < N; i++) { M[i] = true; } for (int i = 2; i < N; i++) { if (M[i]) { for (int j = i * 2; j < N; j += i) { M[j] = false; } } } }
时间复杂度：O(nloglogn)
3.线性素数筛选（欧拉筛）
在埃氏筛法的思想上，这个方法可以保证每个合数都被它最小的质因数筛去，所以一个数只会经过一次。
比如12，既是2的倍数，也是3的倍数，在埃氏筛中，会被2和3筛选两次，而在欧拉筛中12只会被6*2筛选，而不会被4*3筛选。
时间复杂度为O(n)，其实对于埃氏筛，loglogn非常小，我们能碰到的问题级别，区别其实不太大（loglog(10^10) ≈ 5.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; //假设出现i%prime[j]==0，就是 prime[j]|i，一定有 prime[j]|i*prime[j+1]，这里的break，就做到了保证每个合数被它最小的质因数筛去 } } }
拓展应用
上述算法的除去打素数表，我们可以根据算法的思想做一些别的事情。
（1）埃氏筛，获取1~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
费马小定理：
根据逆反命题的等价性，不满足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个，这个数目不到刚才的1/4。这告诉我们如果同时验证a=2和a=3两种情况，算法出错的概率降到了0.000025。容易想到，选择用来测试的a越多，算法越准确。通常我们的做法是，随机选择若干个小于待测数的正整数作为底数a进行若干次测试，只要有一次没有通过测试就可以判定不是素数。这就是费马素性测试。
但是居然就有这样的合数，假设为n，它可以通过所有a（小于n，且满足(gcd,n)=1的数）的测试（这个说法不准确，详见我在地核楼层的回复）。而且第一个这样极端的伪素数小得惊人，仅仅是一个三位数，561。前10亿个自然数中这样的数有600多个。
Miller和Rabin两个人的工作让Fermat素性测试迈出了革命性的一步，建立了传说中的Miller-Rabin素性测试算法。新的测试基于下面的定理：
二次探测定理：
算法描述：
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; } }
- 还没有人评论，欢迎说说您的想法！
客服
