【算法】判断小于n的正整数中有几个质数

这个算法比较简单,关键在于你怎么判断一个正整数是不是质数。这里用的方法是,用小于它的正整数去除它,如果余数有0出现,那说明它是质数,反之,它不是质数。

关键在于,你这个小于它的整数取到哪里,其实取到它的平方根,就足以说明问题了。

#include <iostream>

using namespace std;

class Solution {

public:

    

    int countPrimes(int n) {

    int count=0;

    int i=0;

    int t=0;

        if (n==0 || n==1)

            count=0;

        else

        {

            for(i=2; i<n; i++)

            {

                 for (t=2; t*t<=i;t++)              //从这里开始判断,这个数也就是 i,是不是质数

{

                         if (i%t==0)                         //让i开始除t,判断余数是否为0;t的取值是从2一直到小于等于i的平方根

        break;                //如果余数有0的出现,那i就不是质数,直接跳出for循环

}

if (t*t>i)                     //如果t的平方都大于i了,还没出现余数为0,那就说明i是个质数

                        count+=1;                          //这种情况,我们让count加1

                        cout<<i<<“is a prime”<<endl;

}

              }

 }

        return count;

    }

};

int main()

{

    Solution test;

    cout << test.countPrimes(18);

   return 0;

}

    原文作者:onlyongwang
    原文地址: https://blog.csdn.net/onlyongwang/article/details/80917788
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞