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

2024-04-05 02:36
文章标签 质数 约数 数学知识

本文主要是介绍数学知识--(质数,约数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

目录

一.质数的判定

二.分解质因数

三.质数筛

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;
}

 

这篇关于数学知识--(质数,约数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/877446

相关文章

js算法题,给任意一个偶数,找出他的所有的质数因子

/*给任意一个偶数,找出他的所有的质数因子*/ function primeFactor(n){     var factors=[],            divistor=2;     if(typeof n !=='number'||!Number.isInteger(n)){          return 0;     }; //如果不是偶数返回0,如果是0,返回0

学习算法需要数学知识吗?

目录 算法与数学:看似不可分割的关系常见算法中的数学元素案例分析:不需要高深数学知识的算法1. 二分查找2. 深度优先搜索 (DFS)3. 动态规划:斐波那契数列 如何在有限的数学背景下学习算法1. 专注于算法的逻辑和过程2. 可视化算法流程3. 从简单的实现开始,逐步优化4. 学习算法设计模式5. 实践,实践,再实践6. 关注实际应用 数学如何帮助我们更好地理解和设计算法1. 算法复杂度

算法---计数质数(Java)

题目:计数质数 给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。 示例 1: 输入:n = 10 输出:4 解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 示例 2: 输入:n = 0 输出:0 示例 3: 输入:n = 1 输出:0 提示: 0 <= n <= 5 * 106 解决方法:(埃氏筛) 思路: 算法由希腊数学家厄拉多塞(\rm

leetcode 204:计数质数

int countPrimes(int n) {if(n<=0)return 0;int c=0;for(int i=2;i<n;i++){int flag=0;for(int j=2;j<=std::sqrt(i);j++){if(i%j==0){flag=1;break;}}if(flag==0)c++;}return c;}

第九届中国大学生程序设计竞赛(秦皇岛)-(CCPC2023-Qinhuangdao F - 质数之谜(DP)

题意 给定一个序列,修改最少数量的元素使得任意i属于[1,n-1],q[i]+q[i+1]都为质数,输出最小修改次数 思路 首先手玩的过程中可以发现,     如果因为前面一个数字和自己相加不是质数然后我把自己变成了奇数,那么如果我后面一个数字是偶数     可以发现自己肯定能找到另一个奇数使得和前面相加互质并且和后面相加也互质     举个例子:假设为2 8 10,我此时是8,我发现2+

力扣刷题--762. 二进制表示中质数个计算置位【简单】

题目描述🍗 给你两个整数 left 和 right ,在闭区间 [left, right] 范围内,统计并返回 计算置位位数为质数 的整数个数。 计算置位位数 就是二进制表示中 1 的个数。 例如, 21 的二进制表示 10101 有 3 个计算置位。 示例 1: 输入:left = 6, right = 10 输出:4 解释: 6 -> 110 (2 个计算置位,2 是质数) 7

《算法竞赛进阶指南》0x32_2约数

定义 ∀ a , b ∈ N , 若 g c d ( a , b ) = 1 , 则称 a , b 互质 \forall a,b \in \mathbb{N},若gcd(a,b)=1,则称a,b互质 ∀a,b∈N,若gcd(a,b)=1,则称a,b互质。 对于三个数或更多个数的情况,我们把 g c d ( a , b , c ) = 1 gcd(a,b,c)=1 gcd(a,b,c)=1的情况称

SAT数学知识范围分析

为了方便广大考生更好的复习,小编整理了SAT数学考题知识范围增量分析,以供各位考生备考SAT数学,希望对考生复习有所帮助。   美国高考SAT于今年3月份推出了新的SAT考试形式及内容,其中数学部分的考题范围与难易程度有所提高。以前的SAT数学考试程度仅相当于国内初三的数学水平,主要考学生的四则运算、因数、分数、百分数、小数及比率比值的基本知识及运算能力。这些数学的基本知识,对国内初三学生来

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

定义 若一个正整数无法被除了1和它本身之外的任何自然数整除,则称这个数为质数(素数),反之为合数。 对于一个足够大的整数N,不超过N的质数大约有 N/lnN个,分布比较松散。 质数的判定 试除法 若一个正整数N为合数,则存在一个能整除N的数T,其中 2 ≤ T ≤ N 2\leq T \leq \sqrt{N} 2≤T≤N ​。 因此,我们只需要扫描 [ 2 , N ] [2,\sqr

约数个数a

给定 nn 个正整数 aiai,请你输出这些数的乘积的约数个数,答案对 109+7109+7 取模。 输入格式 第一行包含整数 nn。 接下来 nn 行,每行包含一个整数 aiai。 输出格式 输出一个整数,表示所给正整数的乘积的约数个数,答案需对 109+7109+7 取模。 数据范围 1≤n≤1001≤n≤100, 1≤ai≤2×1091≤ai≤2×109 输入样例: 32