首页 > 其他分享 >数学知识--(质数,约数)

数学知识--(质数,约数)

时间:2024-04-04 23:02:42浏览次数:34  
标签:约数 筛法 -- 质数 int primes mod

本文用于个人算法竞赛学习,仅供参考

目录

一.质数的判定

二.分解质因数

三.质数筛

1.朴素筛法

 2.埃氏筛法

3.线性筛法

 四.约数

1.求一个数的所有约数

2.约数个数和约数之和

3.欧几里得算法(辗转相除法)-- 求最大公约数


一.质数的判定

质数:质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的数。常见的质数有2, 3, 5, 7, 11等。质数也被称为素数。

试除法:时间复杂度:O(n^ 1/2)

bool is_prime(int n)
{
	if (n < 2)
		return false;
	for (int i = 2; i <= n / i; i++) //如果存在 a ÷ b = c , 那么就有 a ÷ c = b; 
	{
		if (n % i == 0)
		{
			return false;
		}
	}
	return true;
}

二.分解质因数

 

试除法:时间复杂度:O(n^ 1/2)

//存放分解后质数的个数
unordered_map<int, int> primes;

void divide(int n)
{
	//从2开始试除
	for (int i = 2; i <= n / i; i++)// i^2 <= n
	{
		//合数进不来,因为被前面的质数约去了
		if (n % i == 0)
		{
			while (n % i == 0)
			{
				primes[i]++;
				n /= i;
			}
		}
	}
	if (n > 1)
		primes[n]++;
}

int main()
{
	divide(84);
	for (auto prime: primes)
	{
		cout << prime.first << ':' << prime.second << endl;
	}

	return 0;
}

三.质数筛

问题:给定一个n,筛出2~n的所有质数

1.朴素筛法

假设一个数n,它的因数有a, 那么n的因数a一定小于n,所以只需要通过a的倍数就能筛掉n,所以朴素筛法就是从2到n筛掉它们的倍数,最后剩下的就是质数。

时间复杂度:N(1 + 1/2 + 1/3 + ... + 1/n) = N*lnN,  O(N*lnN);

 可以发现同一个数可能会被筛掉多次,当样本个数非常多的时候是非常浪费时间的,要如何优化降低对一个数筛的次数呢?

 2.埃氏筛法

埃氏筛法是对上面朴素筛法的优化,只筛掉质数的倍数,来减少筛掉同一个数的次数。

埃氏筛法(Sieve of Eratosthenes)是一种用来找出一定范围内所有素数的算法。其基本思想是从2开始,不断地将质数的倍数标记为非质数,最终剩下的即为质数。

 筛掉4的倍数时,其实在筛掉2的倍数时就筛掉了,因为4是2的倍数,4的倍数也是2的倍数,所以4就没必要再去筛掉它的倍数了;对于一个合数,总会有它的质数代替它来筛掉它的倍数。

质数定理指出,小于给定数n的质数个数约为 n / ln(n)。

优化后时间O(N*loglogN)

const int N = 100;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (st[i]) 
			continue;
		primes[cnt++] = i;
		for (int j = i + i; j <= n; j += i)
			st[j] = true;
	}
}

 

 我们发现还是存在对同一个数多次筛掉的情况,如12被2和3筛掉两次,还能再优化吗?

3.线性筛法

线性筛法是一种在O(n)的复杂度情况下,筛选出2~n的所有质数。
它的原理是,从2开始,每次找到一个最小的质数,然后把它的倍数都标记为非质数,即每个数合数只会被它的最小质因数筛掉。

比如上面的埃氏筛法,12会被2和3筛两次,线性筛法只会通过12的最小的质数2来筛掉。

最外层for循环遍历2~n,primes保存2~i的质数,内层for循环从小枚举质数

1.对于   primes[j] <= n / i;

如果i是合数,会走到 if (i % primes[j] == 0) break  结束掉

如果i是质数,会走到 primes[j] == i 后结束掉

所以不用担心存在越界问题 

2.对于  if (i % primes[j] == 0) break;

若 i % primes[j] != 0, primes[j]一定小于i的最小质因子,primes[j] 一定是primes[j] * i 的最小质因子,因为primes从小到大枚举,且primes[j] 小于i

若i % primes[j] == 0,primes[j] 一定是i的最小质因子,primes[j] 一定是primes[j] * i 的最小质因子,因为primes从小到大枚举,且primes[j] 小于i

如果i % primes[j] == 0,就应该break了,为什么?

已知i % primes[j] == 0,就说明i是合数,i已经再前面通过k * primes[j] 筛掉了;

假设我们没有break,走到primes[j + 1], 会有 i * primes[j + 1], 代入得 k * primes[j] * primes[j + 1],很明显primes[j] < primes[j + 1], 说明一个数已经被primes[j] 筛掉过了,再通过primes[j]筛就重复了。

3.对于每一个合数x,一定会被筛掉,假设x的最小质因子为p,当i 遍历到x / p时,x一定会被筛掉。

4.每一个合数都会被它的最小质数筛掉,说明每个数只会被筛一次,所以是线性的,时间复杂度是O(n)。

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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

 四.约数

1.求一个数的所有约数

试除法:枚举 i <= n / i, 看i 是否是约数

vector<int> get_divisors(int n)
{
	vector<int> result;
	for (int i = 2; i <= n / i; i++)
	{
		if (n % i == 0)
		{
			result.push_back(i);
			//避免加入同一个数
			if (n / i != i)
				result.push_back(n / i);
		}
	}
	sort(result.begin(), result.end());
	return result;
}

2.约数个数和约数之和

给定一个数N,求N的约数个数

将N进行质因数分解p,有N = p1^c1 * p2^c2 * ... *pk^ck
对于每个质数p,c可以取0~c,则约数个数: (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和: (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

 思路:

由N = p1^c1 * p2^c2 * ... *pk^ck,约数和为(p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

p比较好求,直接分解质因数就行,问题是(pk^0 + pk^1 + ... + pk^ck)要怎么求?

假设 t = 1,存在操作 t = p * t + 1;

则有t = p * 1 + 1 = p + 1

t = p * (p + 1) + 1 = p^2 + p + 1

t = p * (p^2 + p + 1) + 1 = p^3 + p^2 + p^1 + 1

……

typedef long long LL;
int mod = 1e9 + 7;

int main()
{
	unordered_map<int, int> primes;
	int n;
	cin >> n;
	while (n--)
	{
		int a;
		cin >> a;
		//对每个数进行质因数分解
		for (int i = 2; i <= a / i; i++)
		{
			if (a % i == 0)
			{
				primes[i]++;
				a /= i;
			}
		}
		if (a > 1)
			primes[a]++;
	}
	LL result = 1;
	for (auto prime : primes)
	{
		LL t = 1;
		int a = prime.first, b = prime.second;
		while (b--)
		{
			t = (t * a + 1) % mod;
		}
		result = result * t % mod;
	}
	cout << result << endl;
	return 0;
}

常见模运算

(a * b) mod c = ((a mod c) * (b mod c)) mod c
(a + b) mod c = ((a mod c) + (b mod c)) mod c
(a - b) mod c = ((a mod c) - (b mod c)) mod c
(a ^ b) mod c = ((a mod c) ^ b) mod c
(a / b) mod c != ((a mod c) / (b mod c)) mod c除法的模运算不满足这样的等式

3.欧几里得算法(辗转相除法)-- 求最大公约数

gcd(a, b) = gcd(b, a mod b);

gcd代表最大公约数

int gcd(int a, int b)
{
	//if (a < b) swap(a, b);//这一步不需要,因为会自己调整,比如gcd(6,16),下一次递归就变成了gcd(16,6)
	return b ? gcd(b, a % b) : a;
}

 

标签:约数,筛法,--,质数,int,primes,mod
From: https://blog.csdn.net/cookies_s_/article/details/137374356

相关文章

  • javaWeb项目-家政服务管理系统功能介绍
    项目关键技术开发工具:IDEA、Eclipse编程语言:Java数据库:MySQL5.7+框架:ssm、Springboot前端:Vue、ElementUI关键技术:springboot、SSM、vue、MYSQL、MAVEN数据库工具:Navicat、SQLyog 1、B/S结构简介B/S结构最大的优点它不需要安装任何的系统,它所有的客户端就只是浏......
  • 基于springboot实现社区医院信息平台系统项目【项目源码+论文说明】
    基于springboot实现社区医院信息平台系统演示摘要随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了社区医院信息平台的开发全过程。通过分析社区医院信息平台管理的不足,创建了一个计算机管理社区医院信息平台的方案。文章介......
  • Matlab|储能辅助电力系统调峰的容量需求研究
    目录1 主要内容目标函数约束条件2 部分代码3 程序结果4下载链接1 主要内容该程序参考文献《储能辅助电力系统调峰的容量需求研究》,主要是对火电、风电和储能等电力设备主体进行优化调度,在调峰能力达不到时采用弃负荷,程序以发电成本、投资运维成本、弃风惩罚、......
  • 基于springboot实现足球青训俱乐部管理后台系统项目【项目源码+论文说明】
    基于springboot实现足球青训俱乐部管理系统演示摘要随着社会经济的快速发展,人们对足球俱乐部的需求日益增加,加快了足球健身俱乐部的发展,足球俱乐部管理工作日益繁忙,传统的管理方式已经无法满足足球俱乐部管理需求,因此,为了提高足球俱乐部管理效率,足球俱乐部管理后台系统应......
  • 帝国CMS模板源码整站安装说明
    安装步骤第一步:先把得到的文件解压缩,把文件通过FTP传到空间里。(请不要把类似ecms014.cncobo.com这个文件夹传到FTP,请传这个大文件夹下面的所有文件夹和文件到空间根目录,请不要上传到2级目录,除非你自己会改模板CSS和JS调用相对地址!)第二步:浏览器键入你的域名或者IP/e/install/inde......
  • 【RISC-V 指令集】RISC-V 向量V扩展指令集介绍(四)- 配置和设置指令(vsetvli/vsetivli
      1.引言以下是《riscv-v-spec-1.0.pdf》文档的关键内容:这是一份关于向量扩展的详细技术文档,内容覆盖了向量指令集的多个关键方面,如向量寄存器状态映射、向量指令格式、向量加载和存储操作、向量内存对齐约束、向量内存一致性模型、向量算术指令格式、向量整数和浮点算术......
  • 玩家角色——播放一次性特效(灰尘)
    目标灰尘特效资源处理角色蓝图添加灰尘特效挂点角色动画添加灰尘特效通知角色蓝图添加二段跳灰尘特效逻辑核心思路之前做过一个播放一次性特效的蓝图,使用生成Actor的节点来使用这个蓝图,其中跑步特效和落地的特效采用动画通知的方式来制作二段跳在角色蓝图中制作(因为第一......
  • 蓝桥杯第十三届单片机省赛真题(IAP15F2K61S2)
    一、题目二、题目分析1、难点(笔者个人认为)(1)s17按键短按和长按的设置不同,界面不同s17短按在参数界面需要把温度参数-1;s17长按在时间界面需要显示分,秒界面;所以笔者这里把两个数码管显示分两个函数voidNixie_Show()//数码管显示函数{ Nixie_pos_num(1,16); Nixie_po......
  • 论文都分哪些级别?
    第一级(T类):特种刊物论文指在《SCIENCE》和《NATURE》两本期刊上发表的论文。发表难度:∞ 第二级(A类):权威核心刊物论文指被国际通用的 SCIE、EI、ISTP、SSCI以及A&HCI检索系统所收录的论文;或在国内具有权威影响的中文核心刊物上发表的论文(不含报道性综述、摘要、消息等)。发......
  • 【RISC-V 指令集】RISC-V 向量V扩展指令集介绍(五)- 向量加载和存储
      1.引言以下是《riscv-v-spec-1.0.pdf》文档的关键内容:这是一份关于向量扩展的详细技术文档,内容覆盖了向量指令集的多个关键方面,如向量寄存器状态映射、向量指令格式、向量加载和存储操作、向量内存对齐约束、向量内存一致性模型、向量算术指令格式、向量整数和浮点算术......