当前位置:   article > 正文

C++常见的质数判断算法_c++判断质数

c++判断质数

        质数定义:一个大于1的自然数,除了1和它本身外,不能被其他自然数(质数)整除。

        算法1:(定义)判断一个整数n是否为质数,只需用2到n-1之间的每一个整数去除,如果都不能被整除,那么n就是一个质数

  1. #include <iostream>
  2. #define MAX 100
  3. using namespace std;
  4. int main() {
  5. int j;
  6. for (int i = 2; i <= MAX; i++) {
  7. for (j = 2; j < i; j++) {
  8. if (i % j == 0)
  9. break;
  10. }
  11. if (j == i)
  12. cout << i << endl;
  13. }
  14. return 0;
  15. }
        算法2:(质数筛选定理)n不能够被不大于根号n的任何质数整除,则n是一个质数

  1. #include <iostream>
  2. #include <cmath>
  3. #define MAX 100
  4. using namespace std;
  5. int main() {
  6. for (int i = 2; i <= MAX; i++) {
  7. float temp = static_cast<float>(i);
  8. int mid = static_cast<int>(sqrt(temp)); //sqrt函数参数和返回值均没有int型。
  9. int j;
  10. for (j = 2; j <= mid; j++) {
  11. if (i % j == 0)
  12. break;
  13. }
  14. if (j > mid)
  15. cout << i << endl;
  16. }
  17. return 0;
  18. }

上面的算法还能改进,因为偶数都不是质数,运算量会下降一半。

        算法2改进:

  1. #include <iostream>
  2. #include <cmath> // for sqrt()
  3. #define MAX 100
  4. using namespace std;
  5. int main() {
  6. cout << 2 << endl; //2是质数
  7. for (int i = 3; i <= MAX; i += 2) { //偶数不是质数,步长可以加大
  8. float temp = static_cast<float>(i);
  9. int mid = static_cast<int>(sqrt(temp));
  10. int j;
  11. for (j = 3; j <= mid; j += 2)//i是奇数,当然不能被偶数整除,步长也可以加大。
  12. if (i % j == 0)
  13. break;
  14. if (j > mid)
  15. cout << i << endl;
  16. }
  17. return 0;
  18. }

        算法3:Miller-Rabin算法

        Miller-Rabin算法是目前主流的基于概率的素数测试方法。素数测试算法主要分两种:概率素数测试算法和真素数测试算法。 概率素数测试算法的特点是:算法速度较快、原理简单、易于编程实现、有一定的误判概率。与之相比,真素数 测试算法最大的特点是不存在误判,但从应用角度讲,真素 数测试算法不如概率测试算法实用。最大的原因是:真素数 测试算法相对较慢。

        Miller-Rabin算法理论艰深,但是实际应用还是比较多,后续再学习。



声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/75330
推荐阅读
相关标签
  

闽ICP备14008679号