数论

2024-06-03 05:20| 来源: 网络整理| 查看: 265

一、质数

【相关概念】

因数：一整数被另一整数整除,后者即是前者的因数,如1,2,4都为8的因数倍数：一个数能够被另一数整除，这个数就是另一数的倍数。如15能够被3或5整除，因此15是3的倍数，也是5的倍数。质数：一个数除了1和它本身没有其他的因数，就叫质数。如2，3，5，7，和数：一个数除了1和它本身还有其他的因数，（至少有3个因数）就叫合数。如4，6，8，9

1.质数的判断（1）质数的判断——枚举法 //根据质数定义判断一个数是否为质数 O(n) bool is_prime(int n) // 判定质数 { if(n < 2) return false; for (int i = 2; i < n; i ++ ) { if(n % i == 0) return false; } return true; } （2）质数的判断——试除法

上述短除法是从头到尾枚举判断，时间复杂度相对很高，其实没有必要枚举1~n所有的数然后判断！

思路:

把1~根号n之间的数都找一遍，看看有没有一个数是n的因子，之所以找到根号n，是因为因子都是成对出现的，假设i是n的因子，那么在根号n后面必定有一个数n/i是n的因子。（只枚举每一对因子中较小的数）。

i | n 那么 n/i | n ，即枚举i的范围从2~n/i即可（只枚举每一对因子中较小的数）

i*i

【本文地址】

公司简介

联系我们