红魔咖啡馆


头发越掉越多，头发越掉越少

【数学】质数

  • ~8.23K 字
  1. 1. 定义
  2. 2. 性质
  3. 3. 判断质数
    1. 3.1. 较小数据范围
    2. 3.2. 较大数据范围
  4. 4. 质因数分解
    1. 4.1. 因数分解
  5. 5. 质数筛
    1. 5.1. 埃氏筛
    2. 5.2. 欧拉筛
    3. 5.3. 分段筛法
  6. 6. 筛法求约数个数
    1. 6.1. 约数个数定理
    2. 6.2. 实现
  7. 7. 筛法求约数和

定义

设整数。如果 p除了平凡约数外没有其他约数，那么称p 为 素数（不可约数)。

若整数 。且 a不是素数，则称a为 合数。

若整数的因数是素数，则该素数称为该整数的素因数

性质

  • 大于 1 的整数 a是合数，等价于存在整数 (d,e)（(1<d,e<a)）使得

  • 若素数 p有大于 1 的约数 (d)，则 （即素数只有 1 和它自身为约数）

  • 任意大于 1 的整数 a都可以表示为素数的乘积：

  • 对于合数 a，一定存在素数 使得

  • 素数有无穷多个。

  • 所有大于 3 的素数都可以表示为

判断质数

较小数据范围

从第一个质数2开始验证，一个个验证待测数n是否能被每个数整除，若任何一个可以整除n，则不是质数

注意，只需要验证到即可

因为若一个数x已经验证无法整除n，则对应的之后的数无需验证，因为此时这之后的因子与x相乘的结果一定大于n，一直到，，故该后面的都不需要验证

1
2
3
4
5
6
7
bool isPrime(long long n){
    if(n<=1) return false;
    for(long long i = 2; i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

较大数据范围

对于较大的数字，可以使用Miller-Rabin测试

过程：

  • 每次选择1~n-1上的随机数字，或者指定一个比n小的质数进行测试
  • 经s次（一般20次以内）得到，s越出错概率越低，速度越慢

对于Java用户，其BigInteger类型内自带了一个判断质数的方法isProbablePrime(s)，使用的测试方法就包含了Miller-Rabin测试，对于大于1e9的数据也不会出现溢出

对于CPP用户，需要使用__int128

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef __int128 ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
ll n;
template<typename T> inline T read() {
    T x = 0, f = 1; char ch = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch - '0');
    return x * f;
}

template<typename T> inline void write(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
ll qpow(ll a, ll n, ll mod){
  ll re = 1;
  while(n){
    if(n&1) re = (re*a)%mod;
    a = (a*a)%mod;
    n>>=1;
  }
  return re%mod;
}
vector<ll> p ={2,3,5,7,11,13,17,19,23,29,31,37};
bool miller_rabin(ll n){
  if(n<3||n%2==0) return n==2;
  ll u = n-1, t = 0;
  while(u%2==0) u/=2, t++;
  for(auto a:p){
    if(n==a) return 1;
    if(n%a==0) return 0;
    ll v = qpow(a, u, n);
    if (v==1) continue;
    ll s = 1;
    for(; s<=t;s++){
      if(v==n-1) break;
      v = (v*v)%n;
    }
    if(s>t) return 0;
  }
  return 1;
}
void solve() {
  n = read<ll>();
  if(miller_rabin(n)) puts("Yes");
  else puts("No");

  
}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  ll tomorin=read<ll>();
  while (tomorin--) solve();
  return 0;
}

质因数分解

对于数n，因数是成对分布的，故可以枚举每一个数i到，若是合数说明i是他的一个质因子，让，直到无法再除，证明将当前质因子对应的因数除尽，再试下一个i

1
2
3
4
5
6
7
8
9
void f(int n){
    for (int i = 2; i*i<=n;i++){
        if(n%i==0){
            cout << i << endl;
            while(n%i==0) n/=i;
        }
    }
    if(n>1) cout << n << endl;
}

注意，若已经有一个素数表，时间复杂度将会从下降为

因数分解

进一步的，我们可以进行因数分解

1
2
3
4
5
6
7
8
9
10
11
void f(int n)
{
    for (int i = 2; i*i<=n; i++)
    {
        if (n%i==0)
        {
            cout << i << endl;
            if (i!=n/i) cout<< n/i << endl;
        }
    }
}

这样的时间复杂度仍为

质数筛

埃氏筛

用一个vis数组标记是质数还是合数，默认都是质数

从第一个质数2开始，计算，，这些数肯定是合数，将这些数对应的vis标记为合数，再遍历操作下一个质数

注意：每次标记只需要从质数开始往后每次加即可，因为前面的肯定被小于该数的质数标记过了

另外，由于偶数除了2都是合数，我们可以选择跳过偶数来让内存和操作需求都减半

另另外，由于bitset的连续读写效率，我们可以将bool数组改为bitset来将布尔值压到一个bit中，可以显著减少内存消耗，这种方法称为位级压缩

时间复杂度：

1
2
3
4
5
6
7
8
9
10
vector<bool> prime(N, true);
void ehrlich(int n){
  for (int i = 2;i*i<=n;i++){
    if(prime[i]){
      for(int j = i*i;j<=n;j+=i){
        prime[j]=false;
      }
    }
  }
}

若只是计数，埃氏筛还可以改进：我们可以预估质数数量，若发现更多合数就减掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 注意此时true表示合数
vector<bool> prime(N, false);
int ehrlich(int n){
  int cnt = (n+1)/2; // 默认偶数都是合数
    // 只需要判断奇数
  for (int i = 3;i*i<=n;i+=2){
    if(!prime[i]){
        // 只需要判断奇数
      for(int j = i*i;j<=n;j+=2*i){
          if(!prime[j]){
              prime[j]=true;
              cnt--;
          }
      }
    }
  }
}

欧拉筛

埃氏筛也有重复筛的情况，因此会慢一些

而欧拉筛保证了每个合数只被自己的最小质因子筛掉

时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<bool> prime(N, true);
void eular(int n){
  int tprime[n/2+1];
  int cnt = 0;
  for (int i = 2;i<=n;i++){
    if(prime[i]){
      tprime[cnt++]=i;
    }
    for(int j = 0; j<cnt;j++){
      if(i*tprime[j]>n)break;
      prime[i*tprime[j]]=false;
      if(i%tprime[j]==0) break;
    }
  }
}

分段筛法

普通的线性筛在数据范围很大的时候会超时或耗尽内存，此时我们需要使用分段筛

思想：用普通筛筛出内的所有质数，然后将所需区间[l, r]分成一段或多段，并对段进行标记，用筛出的质数标记段中合数，并统计没被标记的质数即可

步骤：设右区间为r

  1. 计算，用筛筛出这之内的数
  2. 定义布尔数组标记合数（初始都设为false，表示为可能质数），长度为
  3. 对每个质数
    • 若1ll*p*p>r则可以提前break，因为超出区间右端
    • 计算[l, r]中第一个需要标记的位置start = max(1LL*p*p, ((l + p - 1) / p) * 1LL * p)，即从区间第一个p的倍数开始，p小的时候也可以避免把p本身标掉
    • 从start开始以p步长标记start-l位置为合数，数组标记为true
  4. 对于l==1时，需要特殊处理数组0下标为合数，因为1不是质数
  5. 最后统计数组中false的位置就是质数

注意：

  1. 要开longlong，避免乘法溢出
  2. 若r和r-l都很大，可以考虑分为多个块，对每个块都进行流程

code例：

洛谷P1835 素数密度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
vector<bool> prime(N, true);
ll tprime[N];
bool vis[N]={};
ll cnt = 0;
// 观察到数据规模2^31，如果单纯用线性筛会导致爆内存
// 这时需要分段筛法
void eular(ll n){
  
  for(ll i =2;i<=n;i++){
    if(prime[i]){
      tprime[++cnt] = i;
    }
    for(ll j = i+i;j<=cnt;j+=i){
      if(i*tprime[j]>n) break;
      prime[i*tprime[j]]=false;
      if(i%tprime[j]==0)break;
    }
  }
}
void solve() {
  ll l, r;
  cin >> l >> r;
  // 首先晒出√2^31内的质数，然后用这些质数作为因子来在l-r范围内筛出合数并标记（i*p为合数）
  // 遍历l-r，没有标记的就是质数
  eular(50000);
  if (l==1) vis[0]=1; // 特判l=1
  for(int i = 1;i<=cnt;i++){
    ll p = tprime[i];
    for(ll j = max(2ll, (l-1)/p+1)*p;j<=r;j+=p){ // 计算在区间 [l,r] 中，应该从哪个数开始把质数 p 的倍数标记为合数（分段筛的起点）
      if(j-l>=0) vis[j-l]=true; // 将l-r移动至0-(r-l)范围内，防止过大的下标爆数组
    }
  }
  ll ans = 0;
  for(ll i = 0;i<=r-l;i++)if(!vis[i]) ans++;
  cout<<ans;
}

筛法求约数个数

用表示的约数个数，表示的最小质因子出现次数

约数个数定理

定理
若 ，则

证明
对每个质因子 ，它的约数有 共 个。由乘法原理可知， 的约数总数就是

实现

由于是积性函数，所以我们可以使用线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
vector<int> pri;         // 存储筛出的素数列表
bool not_prime[N];       // 标记合数
int d[N];                // d[i] 表示 i 的约数个数
int num[N];              // num[i] 表示 i 分解后，最低位质因子 p 在 i 中的幂次

void pre(int n) {
  d[1] = 1;              // 1 的约数个数为 1
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      // i 是素数
      pri.push_back(i);
      d[i] = 2;          // 素数 i 的约数只有 1 和 i 自身，共 2 个
      num[i] = 1;        // i = p^1, 此处最低质因子 p 的幂次为 1
    }
    // 用已知的素数列表，对 i 进行线性筛
    for (int p : pri) {
      if (i * p > n) break;
      not_prime[i * p] = true;   // 标记 i*p 为合数

      if (i % p == 0) {
        // 情况一：p 是 i 的最低质因子，i = … * p^k
        // 那么 i*p = … * p^(k+1)，尾质因子 p 的幂次加 1
        num[i * p] = num[i] + 1;
        // 如果 i 的约数个数为 d[i]，且 i 中 p 的幂次为 num[i]，
        // 那么 i*p 中 p 的幂次就是 num[i]+1
        // 根据约数个数公式：若 n = p1^a1 * p2^a2 *…，d(n)=∏(ai+1)
        // 我们可以在已知 d[i] 的基础上做局部更新：
        //   d[i*p] = d[i] / (num[i] + 0) * (num[i] + 1)
        d[i * p] = d[i] / num[i] * (num[i] + 1);
        break;  // 线性筛保证每个合数只被最小质因子对应的 p 处理一次
      } else {
        // 情况二：p 不是 i 的最低质因子，在 i*p 中 p^1 首次出现
        num[i * p] = 1;
        // 新加了一个质因子 p，故约数个数 d[i*p] = d[i] * 2
        d[i * p] = d[i] * 2;
      }
    }
  }
}

筛法求约数和

表示 的约数和， 表示 的最小质因子的

用线性筛在 时间内计算出 每个正整数的约数和 ，其中
- ；
- 表示将 分解为最小质因子 的幂乘以其它部分后，单独对这段 求和： 其中 ，且 是 的最小质因子。

借助下面这个分块性质：
若且 我们可以在线性筛中同时维护 与 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

vector<int> pri;        // 存储已筛出的素数列表
bool not_prime[N];      // 合数标记
int g[N], f[N];         // g[i]：i 中最小质因子 p 的 1+p+...+p^k 和
                        // f[i]：i 的约数和

void pre(int n) {
  // 初始化：1 的约数和为 1，g[1]=1
  g[1] = f[1] = 1;

  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      // i 是素数 p
      pri.push_back(i);
      // 对于素数 p：
      //   g[p] = 1 + p
      //   f[p] = 1 + p
      g[i] = i + 1;
      f[i] = i + 1;
    }
    // 用已筛出的素数列表对 i 进行线性筛
    for (int p : pri) {
      if (i * p > n) break;
      int ip = i * p;
      not_prime[ip] = true; // 标记合数

      if (i % p == 0) {
        // 情况一：p 是 i 的最小质因子，即 i = p^k * x
        // 那么 ip = p^(k+1) * x，x 与 p 互素
        // g[i] = 1 + p + ... + p^k
        // 则 g[ip] = 1 + p + ... + p^k + p^(k+1) = g[i]*p + 1
        g[ip] = g[i] * p + 1;
        // f[ip] = f(x) * g[ip]，而 f[i] = f(x)*g[i]
        // 故 f[ip] = f[i] / g[i] * g[ip]
        f[ip] = f[i] / g[i] * g[ip];
        // 线性筛关键：找到 i 的最小质因子后立即 break
        break;
      } else {
        // 情况二：p 不是 i 的最小质因子，i 与 p 互素
        // ip 增加了一个新的质因子 p^1
        // g[ip] = 1 + p
        // f[ip] = f[i] * f[p] = f[i] * (1+p)
        g[ip] = 1 + p;
        f[ip] = f[i] * f[p];
      }
    }
  }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
赞助喵
非常感谢您的喜欢！
赞助喵