《算法竞赛进阶指南》0x31质数

2024-08-29 09:52

本文主要是介绍《算法竞赛进阶指南》0x31质数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

定义

若一个正整数无法被除了1和它本身之外的任何自然数整除,则称这个数为质数(素数),反之为合数。
对于一个足够大的整数N,不超过N的质数大约有 N/lnN个,分布比较松散。

质数的判定

试除法
若一个正整数N为合数,则存在一个能整除N的数T,其中 2 ≤ T ≤ N 2\leq T \leq \sqrt{N} 2TN

因此,我们只需要扫描 [ 2 , N ] [2,\sqrt{N}] [2,N ]之间的所有整数,一次检查能否整除N,若不能则N是质数,否则N是合数。

bool is_prime(int n)
{if (n < 2) return false;for (int i = 2; i <= sqrt(n); i ++ )if (n % 2 == 0) return false;return true;
}

质数的筛选

给定一个整数N,求出[1,n]之间所有的质数,称为质数的筛选问题。

Erathosthenes筛法
Erathosthenes筛法基于这样的思想,任意整数x的倍数都不是质数,我们可以从2开始,从小到大扫描每一个数,把他们的倍数标记为合数。当扫描到一个数时,如果没有被标记,那么就是质数。

void primes(int n)
{memset(st, 0, sizeof st);for (int i = 2; i <= n; i ++ ){if (st[i]) continue;prime[cnt ++ ] = i;for (int j = i; j <= n / i; j ++ ) st[i * j] = 1;}
}

时间复杂度为 O ( n l o g l o g n ) = n ∗ ( 1 / 2 + 1 / 3 + 1 / 5 + 1 / 7 + . . . + 1 / n ) = n l o g l o g n 时间复杂度为O(nloglogn)=n*(1/2+1/3+1/5+1/7+...+1/n)=nloglogn 时间复杂度为O(nloglogn)=n(1/2+1/3+1/5+1/7+...+1/n)=nloglogn

线性筛法
线性筛法通过“从大到小累积质因子”的方式标记每个合数。
1.依次考虑[2,n]之间的每一个数i。
2.若st[i]=0,说明i是质数,保存下来。
3.扫描每个质数p,令v[i*p]=p.也就是在i的基础上累计一个质因子p。因为p<=i的最小质因子,所以p就是合数i*p的最小质因子。

void primes(int n)
{memset(st, 0, sizeof st);cnt = 0;for (int i = 2; i <= n; i ++ ){if (!st[i]) prime[cnt ++ ] = i;for (int j = 0; i * prime[j] <= n; j ++ ){st[i * prime[j]] = true;if (i % prime[j] == 0) break;}}
}

每个合数i*p只会被最小质因子p筛一次,时间复杂度为O(n)。

质因数分解

任何一个大于1的正整数都能唯一分解成有限个质数的乘积,可写作:
N = p 1 c 1 p 2 c 2 . . . p m c m N=p_1^{c1}p_2^{c2}...p_m^{cm} N=p1c1p2c2...pmcm
其中ci为正整数,pi为质数,且 p 1 < p 2 < . . . < p n p_1 < p_2 < ... <pn p1<p2<...<pn

试除法

void divide(int n)
{m = 0;for (int i = 2; i <= sqrt(n); i ++ ){if (n % 2 == 0){p[ ++ m] = i, c[m] = 0;while (n % i == 0) n /= i, c[m] ++ ;}}if (n > 1) p[ ++ m] = 1, c[m] = 1;for (int i = 1; i <= m; i ++ )cout << p[i] << '^' << c[i] << endl;
}

时间复杂度为 O ( n ) O(\sqrt{n}) O(n )

例题

acwing196.质数距离

如果直接使用线性筛求出[2,r]之间的所有质数的话时间复杂度为T*10^9,显然会超时,我们考虑使用线性筛求出 [ 2 , r ] [2,\sqrt{r}] [2,r ]之间所有的素数,对于每个素数,把[l,r]中能被该质数整除的数标记。

时间复杂度分为两部分,线性筛的时间复杂度加上求区间合数的时间复杂度。
前者时间复杂度为 O ( r ) O(\sqrt{r}) O(r )
后者时间复杂度为 ( r − l ) / 2 + ( r − l ) / 3 + ( r − l ) / 5 + . . . + ( r − l ) / r = O ( ( r − l ) ∗ ( l o g l o g n ) ) (r-l)/2+(r-l)/3+(r-l)/5+...+(r-l)/\sqrt{r}=O((r-l)*(loglog\sqrt{n})) (rl)/2+(rl)/3+(rl)/5+...+(rl)/r =O((rl)(loglogn ))
总和为 O ( T ∗ ( r + ( r − l ) ∗ ( l o g l o g n ) ) ) O(T*(\sqrt{r}+(r-l)*(loglog\sqrt{n}))) O(T(r +(rl)(loglogn )))

#include <iostream>
#include <cstring>
using namespace std;
#define N 1000010
typedef long long ll;
bool st[N];
int prime[N];
int cnt = 0;
void init(int n)
{memset(st, 0, sizeof st);cnt = 0;for (int i = 2; i <= n; i ++ ){if (!st[i]) prime[cnt ++ ] = i;for (int j = 0; i * prime[j] <= n; j ++ ){st[i * prime[j]] = true;if (i % prime[j] == 0) break;}}
}
int main()
{int l, r;while (cin >> l >> r){init(500000);memset(st, 0, sizeof st);for (int i = 0; i < cnt; i ++ ){ll p = prime[i];for (ll j = max(2 * p, (l - 1 + p) / p * p); j <= r; j += p)st[j - l] = true;}cnt = 0;for (int i = 0; i <= r - l; i ++ ){if (!st[i] && i + l >= 2) prime[cnt ++ ]  = i + l;}if (cnt < 2) puts("There are no adjacent primes.");else{int minp = 0, maxp = 0;for(int i = 0; i < cnt - 1; i ++ ){int d = prime[i + 1] - prime[i];if (d < prime[minp + 1] - prime[minp]) minp = i;if (d > prime[maxp + 1] - prime[maxp]) maxp = i;}printf("%d,%d are closest, %d,%d are most distant.\n",prime[minp], prime[minp + 1], prime[maxp], prime[maxp + 1]);}}return 0;
}

acwing197.阶乘分解
首先排除先求出阶乘再用试除法分解质因数的方法。
再排除对于1-n每一个整数分解质因数,最后进行整合的方法,因为这样的时间复杂度为 O ( n n ) O(n\sqrt{n}) O(nn ),依然会超时。
考虑枚举质数,因为N!的阶乘的质因数肯定不会大于N,所以找丛2到N的所有质数p。
对于每一个p^k,求其会贡献多少个质数p的数量,即
⌊ N / p ⌋ + ⌊ N / p 2 ⌋ + ⌊ N / p 3 ⌋ + . . . + ⌊ N / p k ⌋ \lfloor N/p \rfloor+\lfloor N/p^2 \rfloor+\lfloor N/p^3 \rfloor+...+\lfloor N/p^k \rfloor N/p+N/p2+N/p3+...+N/pk
一共有 l o g p n log_p^n logpn项,可以以O(1)的时间求出每一项的值。又因为前n个数中质数数量为n/logn,所以 l o g 2 n + l o g 3 n + l o g 5 n . . . < l o g 2 n ∗ n / l o g 2 n = n log_2^n+log_3^n+log_5^n...<log_2^n *n/log_2^n = n log2n+log3n+log5n...<log2nn/log2n=n
所以总体时间复杂度为 O ( n ) O(n) O(n)

#include <iostream>
using namespace std;
#define N 1000010
bool st[N];
int prime[N];
int n, cnt = 0;
typedef long long ll;
void init(int n)
{for (int i = 2; i <= n; i ++ ){if(!st[i]) prime[cnt ++ ] = i;for (int j = 0; prime[j] * i <= n; j ++ ){st[i * prime[j]] =true;if (i % prime[j] == 0)break;}}
}
int main()
{cin >> n;init(n);for (int i = 0; i < cnt; i ++ ){int p = prime[i];int s = 0;for (ll j = p; j <= n; j *= p)s += n / j;printf("%d %d\n", p, s);}return 0;
}

这篇关于《算法竞赛进阶指南》0x31质数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1117527

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Spring Boot结成MyBatis-Plus最全配置指南

《SpringBoot结成MyBatis-Plus最全配置指南》本文主要介绍了SpringBoot结成MyBatis-Plus最全配置指南,包括依赖引入、配置数据源、Mapper扫描、基本CRUD操... 目录前言详细操作一.创建项目并引入相关依赖二.配置数据源信息三.编写相关代码查zsRArly询数据库数

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

JavaScript错误处理避坑指南

《JavaScript错误处理避坑指南》JavaScript错误处理是编程过程中不可避免的部分,它涉及到识别、捕获和响应代码运行时可能出现的问题,本文将详细给大家介绍一下JavaScript错误处理的... 目录一、错误类型:三大“杀手”与应对策略1. 语法错误(SyntaxError)2. 运行时错误(R

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python使用date模块进行日期处理的终极指南

《Python使用date模块进行日期处理的终极指南》在处理与时间相关的数据时,Python的date模块是开发者最趁手的工具之一,本文将用通俗的语言,结合真实案例,带您掌握date模块的六大核心功能... 目录引言一、date模块的核心功能1.1 日期表示1.2 日期计算1.3 日期比较二、六大常用方法详

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解