教育培训的网站建设,湖南网站建设小公司,诗词门户网站,上海做网站设计公司文章目录1. 素数判定2. 素数筛选法3. 质因数分解4. 求一个数的约数5. 求两个数的最大公约数#xff08;GCD#xff09;6. 求两个数的最小公倍数#xff08;LCM#xff09;1. 素数判定
判定从 2 到sqrt(n)依次能否把 n 整除#xff0c;若存在可以整除的数则说明 n 不是素数…
文章目录1. 素数判定2. 素数筛选法3. 质因数分解4. 求一个数的约数5. 求两个数的最大公约数GCD6. 求两个数的最小公倍数LCM1. 素数判定
判定从 2 到sqrt(n)依次能否把 n 整除若存在可以整除的数则说明 n 不是素数若都不可以整除则说明 n 是素数。
注意2 是特殊的素数。
为什么到sqrt(n)就可以了呢请观察下面两个合数的例子
30 分解为两个因数相乘
2 x 153 x 105 x 66 x 510 x 315 x 2
36 分解为两个因数相乘
2 x 183 x 124 x 96 x 69 x 412 x 318 x 2
发现当越过sqrt(n)后得到的两个因数与sqrt(n)前相同只是位置对调了而已因此没有必要对sqrt(n)后的数进行试除。
#include cstdio
#include cmath
using namespace std;bool isPrime (int x){if (x 2)return true;else{int bound sqrt(x);for (int i 2; i bound; i)if (x % i 0) return false;}return true;
}int main(){int n;while (scanf(%d, n) ! EOF){bool flag isPrime(n);if (flag)printf(Yes\n);elseprintf(No\n);}return 0;
}2. 素数筛选法
原理
2 是素数把 2 后面所有能被 2 整除的数都划去2 后面第一个没划去的数是 3把 3 留下3 后面所有能被 3 整除的数都划去3 后面第一个没划去的数是 5把 5 留下5 后面所有能被 5 整除的数都划去5 后面第一个没划去的数是 7把 7 留下7 后面所有能被 7 整除的数都划去…
注意每次划去当前质数的倍数时可能存在某些数被重复筛选的情况如 8 既被 2 又被 4 筛选。在枚举筛选的时候可以进行剪枝当 i 为素数时注意到i * k (k i)必定已经在求得 k 的某个素数因子时被标记过因此可以从i * i开始。
#include math.h
#include stdio.h
#include string.h#define MAX 10000bool isPrime[MAX1];int main(){int n;scanf(%d, n);memset(isPrime, true, sizeof(isPrime)); // memset函数包含于string.h头文件中 for (int i 2; i sqrt(n); i){if (isPrime[i]){ // 发现是素数下面将素数的倍数都标记为非素数for (int j i * i; j n; j i) // i*k(ki)必定已经在求得k的某个素数因子时被标记过因此从i*i开始 isPrime[j] false;}}for (int i 2; i n; i)if (isPrime[i]) printf(%d , i);return 0;
}3. 质因数分解
输入
994输出
2 7 71代码
#include math.h
#include stdio.h
#include string.h#define MAX 10000bool isPrime[MAX1];int main(){int n;scanf(%d, n);memset(isPrime, true, sizeof(isPrime)); // memset函数包含于string.h头文件中 int bound sqrt(n);// 标记素数 for (int i 2; i bound; i){if (isPrime[i]){ // 发现是素数下面将素数的倍数都标记为非素数for (int j i * i; j n; j i) // i*k(ki)必定已经在求得k的某个素数因子时被标记过因此从i*i开始 isPrime[j] false;}}// 分解质因数for (int i 2; i bound; i){if (isPrime[i]){ // 如果是质数则开始试除 while (n % i 0){ // 若发现能整除则继续使用这个质数除下去 n n / i;printf(%d , i);}}} if (n 1) // 若除完后结果不是1说明剩下来的是质数 printf(%d, n);return 0;
}4. 求一个数的约数
在自然数0和正整数的范围内
4的正约数有1、2、4。
6的正约数有1、2、3、6。
10的正约数有1、2、5、10。
12的正约数有1、2、3、4、6、12。
15的正约数有1、3、5、15。
18的正约数有1、2、3、6、9、18。
20的正约数有1、2、4、5、10、20。
注意一个数的约数必然包括1及其本身。
#include cstdio
#include cmath
using namespace std;int main(){int n;while (scanf(%d, n) ! EOF){for (int i 1; i sqrt(n); i){if (n % i 0){printf(%d %d , i, n / i);}}printf(\n);}return 0;
}5. 求两个数的最大公约数GCD
辗转相除法两个整数的最大公约数等于其中较小的数和两数相除的余数的最大公约数即gcd(a,b) gcd(b, a mod b)。
基本思想分治。
原理若整数 g 为 a、b 的最大公约数则有
a g x l1
b g x m2
a、b 又可以表示为
a b x k r即a / b k···r3
把12代入到3
g x l g x m x k r即r g x (l - m x k)
注意到r a mod b因此a mod b g x (l - m x k)4
联合24这样问题变为了求 b 和 a mod b 的最大公约数
b g x m2
a mod b g x (l - m x k)5
递归写法
// 辗转相除法求最大公约数12和18的最大公约数6
int gcd (int a, int b){if (b 0)return a;elsereturn gcd(b, a % b);
}非递归写法
// 辗转相除法求最大公约数12和18的最大公约数6
int gcd (int a, int b){while (b ! 0){int rem a % b;a b;b rem;}return a;
}6. 求两个数的最小公倍数LCM
// 求最小公倍数12和18的最小公倍数36
int lcm (int a, int b){return a * b / gcd(a, b);
}
