数学知识

2024-07-03 11:30| 来源: 网络整理| 查看: 265

文章目录 1.质数1.1质数的判定---试除法1.2分解质因数---试除法 1.3筛质数2.约数2.1试除法求约数2.2约数个数2.3约数之和2.4最大公约数---欧几里得算法（辗转相除法）

1.质数

质数是针对所有大于1的自然数定义的，在大于1的整数中，如果只包含1和本身这两个约数，就被定义成为质数，或者叫素数。

1.1质数的判定—试除法

一个数的因数都是成对出现的：例如12的因数有3和4,2和6 所以我们可以只枚举较小的那一个，即根下n，假设较小的为d，较大的为n/d；在这里插入图片描述

#include #include using namespace std; bool is_prime(int x) { if (x > x; if (is_prime(x)) puts("Yes"); else puts("No"); } return 0; } 1.2分解质因数—试除法

质因数的定义：在这里插入图片描述

首先我们应该了解一下正常的教学做法：在这里插入图片描述所以我们只需要进行这些步骤的模拟即可，也就是从2开始遍历循环不停的进行除法：步骤详解从2开始往后做除法，第一个能被除开的数一定是原数n的一个质数

for(int i=2;i1那么说明最后的这个n也是n的一个质数为什么可以这样？因为 n中最多只包含一个大于根号n的质因子

if(n>1)printf("%d %d\n",n,1);

代码实现：

若n是合数，那么它的最大的质因子不会超过sqrt(n)。若n是质数，那么它只有一个质因子，且该质因子就是它本身，且大于sqrt(n)。 #include using namespace std; void divide(int n){ for(int i=2;i

【本文地址】

今日新闻