素性测试

1、朴素的素数判断

bool prime(ll n) { if (n <= 1) return false;//特判 for (ll i = 2; i*i <= n; ++i) if (n%i == 0) return false; return true; }

原理不再赘述

判断单个数是不是素数，时间复杂度O(n^(1/2))

2、miller_rabin素性测试

ll gg[8] = {2,3,5,7,13,29,37,89}; ll ksm(ll a, ll k, ll m) { ll r = 1; a = a%m; for (; k; k >>= 1, a = a*a%m) if (k & 1) r = r*a%m; return r; } bool miller_rabin(ll a, ll n)//判断能否通过 { ll d = n-1, r = 0; while (d%2 == 0) d /= 2, ++r; ll x = ksm(a, d, n); if (x == 1) return true; for (ll i = 0; i < r; ++i) { if (x == n-1) return true; x = x*x%n; } return false; } bool is_prime(ll n)//Is-prime判断是否为素数 { if (n <= 1) return false;//特判 for (int i = 0; i < 8; ++i) if (n == gg[i]) return true; for (int i = 0; i < 8; ++i) if (!miller_rabin(gg[i],n)) return false; return true; }

在long long范围内使用 2,3,5,7,13,29,37,89 进行测试够用

放一张以上两种算法效率对比图

miller_rabin素性测试 朴素法 素数个数 花费时间 素数个数 花费时间 1 ~ 10 4 0ms 4 0ms 1 ~ 100 25 0ms 25 0ms 1 ~ 1000 168 1ms 168 0ms 1 ~ 10000 1229 6ms 1229 1ms 1 ~ 100000 9592 46ms 9592 22ms 1 ~ 1000000 78498 491ms 78498 534ms 1 ~ 10000000 664579 5356ms 664579 13567ms

素数筛法

1e8范围

1、朴素筛法

利用上文提及的两种判断素数的方法一个一个判断，效率过低

2、埃式筛法

bool str[100000010]; void prime() { memset(str, 0, sizeof(str)); for(int i = 2; i < 100000010; ++i) if(!str[i]) for(int j = 2*i; j < 100000010; j += i) str[j] = 1; }

时间复杂度O(nloglogn)

3、改进的埃式筛法

bool str[100000010]; void prime() { memset(str, 0, sizeof(str)); for(int i = 2; i*i < 100000010; ++i) if(!str[i]) for(int j = i*i; j < 100000010; j += i) str[j] = 1; }

仔细比较改进前和改进后的埃式筛法

改进后的埃式筛法时间复杂度 O(n)

4、欧式筛法（线性筛）

bool check[1000000010]; vector<int> p; void prime() { for (int i = 2; i < 100000010; ++i) { if(!check[i]) p.push_back(i); for (int j = 0; j < p.size(); ++j) { if (i * p[j] >= 100000010)break; check[i*p[j]] = 1; if (i % p[j] == 0)break; } } }

时间复杂度 O(n)

与改进后的埃式筛法相比，欧式筛法必须在筛的过程中记录素数， 而埃式筛法不用记录

附上以上三种方法的效率对比 （1 ~ 1e8） 三种算法均记录了素数，并计算了素数个数

素数个数 花费时间 埃式筛法： 5761456 2406 ms 改进的埃式筛法： 5761456 1453 ms 欧式筛法： 5761456 1622 ms

改进的埃式筛法甚至超越了欧式筛法 100 ms

5、区间筛法

给定 L，R，对区间 [ L , R ] 进行线性筛法

bool is_prime[100000010]; bool is_prime_small[100000010]; void segment_sieve(ll a,ll b) { for(ll i = 0; i*i <= b; ++i) is_prime_small[i]=false; for(ll i = 0; i <= b-a; ++i) is_prime[i]=false; for(ll i = 2; i*i <= b; ++i) if(!is_prime_small[i]) { for(ll j = 2*i; j*j <= b; j += i) is_prime_small[j] = true; //筛选[2,sqrt(b)); //(a+i-1)/i得到最接近a的i的倍数，最低是i的2倍，然后筛选 for(ll j = max(2LL, (a+i-1)/i)*i; j <= b; j += i) is_prime[j-a] = true; } }

注意对 1 的特判

附一道例题：Prime Distance

题意简述：给定两个整数L,R，求闭区间[L,R]中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。（多组数据）

样例输入 2 17 14 17 样例输出 2,3 are closest, 7,11 are most distant. There are no adjacent primes.

思路分析：利用区间筛法

源代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; bool is_prime[100000010]; bool is_prime_small[100000010]; void segment_sieve(ll a,ll b) { for(ll i = 0; i*i <= b; ++i) is_prime_small[i]=false; for(ll i = 0; i <= b-a; ++i) is_prime[i]=false; for(ll i = 2; i*i <= b; ++i) if(!is_prime_small[i]) { for(ll j = 2*i; j*j <= b; j += i) is_prime_small[j] = true; for(ll j = max(2LL, (a+i-1)/i)*i; j <= b; j += i) is_prime[j-a] = true; } } int main() { ll l, r; while (~scanf("%lld%lld", &l, &r)) { if (l == 1) ++l; segment_sieve(l, r); ll m1, m2; m1 = 1 << 30; m2 = -1; bool flag = true; ll j = 0; ll ans[5] = {0}; for (ll i = l; i <= r; ++i) if (!is_prime[i-l]) { if (flag) j = i, flag = false; else { ans[0] = 1; if (i - j < m1) m1 = i-j, ans[1] = j, ans[2] = i; if (i - j > m2) m2 = i-j, ans[3] = j, ans[4] = i; j = i; } } if (ans[0]) printf("%lld,%lld are closest, %lld,%lld are most distant.\n", ans[1], ans[2], ans[3], ans[4]); else printf("There are no adjacent primes.\n"); } return 0; }