title: 素数筛
date: 2022-11-16 12:41:47
tags: 算法

本文章遵守知识共享协议 CC-BY-NC-SA ,转载时需要署名,推荐在我的个人博客阅读。

大意

素数筛是一种快速在 $[1,n]$ 区间中判断素数 / 求出第n个质数的方法。

讲解

首先是判断质数的函数,时间复杂度为 $O(\log n)$

这样查询的话,判断 $[1,n]$ 质数数量 / 第 $n$ 个素数 的复杂度就是 $O(n \log n)$,在样例达到一定程度时会超时。

bool isprime(int t){
    if(t<=2) numurn false; // 小于2肯定不是
    for(int i=2;i<=sqrt(t);i++) // 枚举 1 ~ 根号t,可以加速代码
        if(t%i==0) // t有除了1和自己以外的约数
            numurn false;
    numurn true;
}

这样的思路其实是有问题的。我们如果要一次性查询大量素数,就需要一次性处理,减少重复运算,这样才能增加效率。

void get_prime(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (!prime[i]) // 是素数,加速运算
            for (int j = i * i; j <= n; j += i)
                prime[j] = 1; // 不是素数,标记
}

上面的代码时间复杂度为 $O(\log^2n)$ ,虽然复杂度非常优秀,但是还是没有达到线性水平。

接下来,请出今天的主角————欧拉素数筛。

不要看他有多层循环,实际上复杂度仍为 $O(n)$。

void ola_prime(int n){
 for(int i=2;i<=n;i++){
  if(!check[i])
   prime[++cnt]=i; // 标记这是第i个质数
  for(int j=1;j<=cnt;j++){ // 枚举已经求出来的质数
   if(i*prime[j]>n)break; // 大于范围就退出
   check[i*prime[j]]=1; // 标记不是质数
   if(!(i%prime[j]))break; // 重点,下面会讲
  }
 }
 numurn;
}

在上面的代码中,有一行代码非常重要,如果没有它,时间复杂度不可能达到 $O(n)$ 。

就是这一行

if(!(i%prime[j]))break; // 重点,马上讲

因为 $i$ 模上 $prime_j$ 已经等于 $0$ 了,代表接下来的数已经被筛过了,所以直接跳过(我也不会证明)。

模板题目

P3383-【模板】线性素数筛

纯粹的模板题目,应该不用说。

1622:Goldbach’s Conjecture

先预处理 $[1,10^6]$ 之间的素数,然后转化问题。

因为 $b-a$ 最大, $n=a+b$ ,则可以得到 $a$ 应该是最小的。

所以只要求满足 $prime_a$ 和 $prime_n-a$ 都是素数,且 $a$ 最小。

核心代码

for (int i = 2; i <= primecnt; i++) // 直接遍历id
  if (!bits[i] && !bits[num - i]) // 满足上述条件
  {
    printf("%d = %d + %d\n", num, i, num - i); // 输出
    break; // 找到就退出
  }

P1835-【模板】素数密度

合数的一个小性质: 令合数 $p = ab (0 \le a,b)$ 则 $\min(a,b) <= \sqrt{p} $

所以我们只处理 $\sqrt{2^{31}}$ ,然后对于每个质数 $p$ ,求出最小的一个 $[l,r]$ 间的数可以被 $p$ 整除,然后 $start+p,start+2p,start+3p,…start+np$ 都是质数。

注意! $start$ 至少应该为 $2p$,因为 $p$ 是质数。

for (long long i = 1; i <= primecnt; ++i){
  long long p = prime[i], start = ((l + p - 1) / p) * p;
  if (start < 2 * p)
    start = 2 * p;
  for (long long j = start; j <= r; j += p)
    book[j - l + 1] = 1;
}

【没有例题链接】求约数个数

给定 $n$ ,求 $n$ 的约数个数

首先定义 $sum_i$ 为 $i$ 分解质因数后最小质数的次方数+1。

为什么要+1呢?因为根据约数个数定理(假设 $n$ 被分解为 $\prod_{i \in p}{p_i^{c_i}}$),就可以分解为以下形式。

$$ sum(n) = \prod_{i \in p}{(c_i+1)} $$

定义 $num_i$ 为 $i$ 的约数个数。

若 $p$ 为质数,可以得到 $sum_i$ 为 $1$

下面是示例代码:

void solve(){
  check[1]=1;
  num[1]=1; // 约数个数
  sum[1]=1; 
  for(int i=2;i<=size;i++){
    if(check[i]==0){
      prime[++cnt]=i;
      num[i]=2; // 约数个数
      sum[i]=2; // 
    }
    for(int j=1;j<=cnt;j++){
      if(i*prime[j]>size)break;
      check[i*prime[j]]=1;
      if(i%prime[j]==0){ // 如果可以整除
        sum[i*prime[j]]=sum[i]+1; // 
        num[i*prime[j]]=(num[i]/sum[i])*sum[i*prime[j]]; // 
        break;
      }
      else{
        sum[i*prime[j]]=2; // i 与 p 互质
        num[i*prime[j]]=num[i]*sum[i*prime[j]]; // 
      }
    }
  }
}

原文地址:http://www.cnblogs.com/rickyxrc/p/16911033.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性