设为首页 加入收藏

TOP

素数判定(一)
2019-01-10 18:09:29 】 浏览:197
Tags:素数 判定

  素数定义:质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。

  素数问题变化莫测,但万变不离其宗。素数问题最核心的就是如何判断一个数是否是素数。对于判断一个数m是否是素数,最原始的方法就是按照素数的定义,试除2开始到m-1的整数,如果无一例外地都不能整除,则该数一定是素数。实现程序如下:

      #include <iostream>
      using namespace std;
    //判断是否是素数
    int main() {
         cout << "please inpout a number.";
    int m;
    cin >> m;
    for (int i = 2; i < m; ++i)
         if (m%i == 0) {
                  cout << m << " isn't a prime\n";
          return 1;
         }
     cout << m << " is a prime\n";
        return 0;
  }
改进:我们知道如果一个数有因子的话,那么在它的平方根数以内就应该有,否则就没有因子。例如66的平方根在8与9之间,因为66不是素数,,则它一定有比8还小的因子,我们知道66的因子是2、3、6等。
 
  现在我们就可以将m试除2到√m的整数,如果无一例外地都不能整除,则该数一定是素数。实现程序如下:
      #include <iostream>
      using namespace std;
    //判断是否是素数
  int main() {
    cout << "please inpout a number.";
    int m;
        &

nbsp;     cin >> m;
              double sqrtm = sqrt(m*1.0);
              for (int i = 2; i < sqrtm; ++i)
                if (m%i == 0) {
                  cout << m << " isn't a prime\n";
                       return 1;
                     }
      cout << m << " is a prime\n";
      return 0;
       }
  改进:现在举个例子,判断102是否是素数,本来要从2试除到10。但事实上,中间的4、6、8、10也都无须试,只需要试除2、3、5、7。直接来说,就是只需要试除2到√m之间的所有素数即可。而所有素数(除了2和3)都满足6*i-1或6*i+1(i=1、2、3...)。那么代码又可以改进,如下:
  #include <iostream>
  using namespace std;
  int main() {
       cout << "please inpout a number.";
       int m;
       cin >> m;
     //两个较小数另外处理
     if (m == 2 || m == 3)
          return 1;
          double sqrtm = sqrt(m*1.0);
     for (int i = 5; i <= sqrtm; i += 6)
        if (m %i == 0 || m % (i + 2) == 0)
           cout << m << " isn't a prime\n";
     cout << m << " is a prime\n";
     return 0;
  } 
  下面这种方法也是本人借鉴别人的,如有侵权请联系我删除。
  改进:素数有2、3、5、7、11、13、17、19、23、29...,观察可知:素数一定在6的倍数的左右,但6的倍数的左右不一定是素数,如23是素数,但25不是素数。则我们可以先通过这个条件将可能是素数的数筛选出来,然后采用方法三,代码如下:
  #include <iostream>
  using namespace std;
  int main() {
       cout << "please inpout a number.";
        int m;
     cin >> m;
     //两个较小数另外处理
     if (m == 2 || m == 3)
           return 1;
     //不在6的倍数两侧的一定不是质数
     if (m % 6 != 1 && m % 6 != 5) {
        cout << m << " isn't a prime\n";
        return 0;
     }
  
     double sqrtm = sqrt(m*1.0);
     //在6的倍数两侧的也可能不是质数
     for (int i = 5; i <= sqrtm; i += 6)
          if (m %i == 0 || m % (i + 2) == 0)
          cout << m << " isn't a prime\n";
      //排除所有,剩余的是质数
      cout << m << " is a prime
编程开发网
首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇让串口调试助手像命令行一样 下一篇剑指Offer整理笔记

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }