质数判断 优化枚举法
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了质数判断 优化枚举法,现在分享给大家,供学习和参考。文章包含535字,纯文字阅读大概需要2分钟。
教程信息
优化枚举算法
判断N是否为质数,只需要判断[2,根号N]中有无因子能够整除N即可
(1)若N是合数,其因子总是两两出现的,一个是a,一个则是N/a。
(2)因此N=a*N/a=根号N*根号N。
(3)a要么大于根号N(N/a一定大于根号N)。要么小于根号N(N/a一定小于根号N),要么等于根号N。
实现代码:
#include <bits/stdc++.h> using namespace std; bool isPrime(int n) { if (n < 2) return false; else if (n == 2) return true; else if (n > 2) { // 优化缩小计算范围 for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return false; return true; } } int main(){ int num=0; cin>>num; cout<<isPrime(num)<<endl; return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供质数判断 优化枚举法的全部内容,希望教程文章能够帮你了解学习质数判断 优化枚举法,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-334.html
发布时间:2024-02-04
更新时间:2024-02-04