admin 管理员组文章数量: 887021
素数
- 微信搜索：编程笔记本
- 微信搜索：编程笔记本
- 微信搜索：编程笔记本
点击上方蓝字关注我，我们一起学编程
欢迎小伙伴们分享、转载、私信、赞赏
小伙伴儿们看完以后可不可以帮我点亮一下在看呀~
1 判断素数
要判断一个整数 num 是否为素数，有几种思路。
- (1) 把 num 被 2 ~ num-1 之间的每一个整数去除，如果都不能被整除，那么 num 就是一个素数。
在这种方法中，有很多非必要的计算。比如，当被除数超过 num 的一半时就不可能整除，所以改进如下。
- (2) 把 num 被 2 ~ num/2 之间的每一个整数去除，如果都不能被整除，那么 num 就是一个素数。
上面两种算法的参考代码如下所示：
bool isPrime1(int num)
{bool isprime = true;for (int i = 2; i <= num - 1; ++i) {if (num % i == 0) {isprime = false;break;}}return isprime;
}bool isPrime2(int num)
{bool isprime = true;for (int i = 2; i <= num / 2; ++i) {if (num % i == 0) {isprime = false;break;}}return isprime;
}
再来分析一下：其实 num 不必被 2 ~ num/2 之间的每一个整数去除，只需被 2 ~ sqrt(num) 之间的每一个整数去除就可以了。如果 m 不能被 2 ~ sqrt(num) 间任一整数整除，num 必定是素数。
原因：因为如果 num 能被 2 ~ num/2 之间任一整数整除，其二个因子必定有一个小于或等于 sqrt(num) ，另一个大于或等于 sqrt(num) 。因此只需判断 2 ~ sqrt(num) 区间的整除性即可。
参考代码：
bool isPrime3(int num)
{bool isprime = true;int k = (int)sqrt((double)num);for (int i = 2; i <= k; ++i) {if (num % i == 0) {isprime = false;break;}}return isprime;
}
注：2021 乐鑫科技提前批的编程题就考到了素数的判断，若不采用第三种解法就会超时。
2. 最大公约数
求解两个整数 a、b 的最大公约数，除蛮力法外，有两种较好的方法。
- (1) 辗转相除法
① a % b == c
② 若 c = 0 ，则返回 b
③ 若 c ≠ 0 ，则 a = b, b = c ，转 ①
参考代码：
- 微信搜索：编程笔记本
- 微信搜索：编程笔记本
- 微信搜索：编程笔记本
int gcd1(int a, int b)
{int c = a % b;while (c != 0) {a = b;b = c;c = a % b;}return b;
}
- (2) 相减法
① 若 a = b ，则返回 a
② 若 a > b ，则 a = a - b ，转 ①
③ 若 a < b ，则 b = b - a ，转 ①
参考代码：
int gcd2(int a, int b)
{while (a != b) {if (a > b) {a -= b;} else {b -= a;}}return a;
}
3 最小公倍数
最小公倍数 = 两整数的乘积 ÷ 最大公约数
重用最大公约数的代码，参考如下：
int lcm(int a, int b)
{int ma = a;int mb = b;while (a != b) {if (a > b) {a -= b;} else {b -= a;}}return ma * mb / a;
}
- 微信搜索：编程笔记本
- 微信搜索：编程笔记本
- 微信搜索：编程笔记本
本文标签： 素数
版权声明：本文标题：素数 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1722926268h735524.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论