204. Count Primes 求素数
专注于为中小企业提供网站设计制作、网站设计服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业鄂尔多斯免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了千余家企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。Description:
Count the number of prime numbers less than a non-negative number, n.
题目大意:
输出小于n的所有素数的个数。
思路:
采用厄拉多筛选法。
西元前250年,希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法,减少了逐一检查每个数的的步骤,可以比较简单的从一大堆数字之中,筛选出质数来,这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。
具体操作:先将 2~n 的各个数放入表中,然后在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数 是5,将它画圈,并划去5的其他倍数……依次类推,一直到所有小于或等于 n 的各数都画了圈或划去为止。这时,表中画了圈的以及未划去的那些数正好就是小于 n 的素数。
其实,当你要画圈的素数的平方大于 n 时,那么后面没有划去的数都是素数,就不用继续判了。
代码实现如下:
class Solution { public: int countPrimes(int n) { bool *Del = new bool[n]; //申请数组用来记录某个数字是否被标记 if(n > 2) Del[2] = false; //先将数字2标记为素数 //某一数字标记为false表示该数为素数。 //某一数字标记为true表示该数为非素数。 for(int i = 3;i=n) break; for(int j = 2;i*j < n; j++) Del[i*j] = true; } } int count = 0; for(int i = 2;i < n;i++) { if(!Del[i]) count++; } delete [] Del; return count; } };
思路2:
耗时太长。
代码如下:
bool isPrimes(int n) { if (n == 2) return true; int middle = (int)sqrt(double(n)); for (int i = 2; i <= middle; i++) { if (n % i == 0) return false; } return true; } void insertUnPrimesToSet(set&myset, int n,int max,int flag) { int times = (max-1) / n; if (flag == 0) { for (int i = 1; i <= times; i++) { myset.insert(n*i); } } else if (flag == 1) { for (int i = 2; i <= times; i++) { myset.insert(n*i); } } } int countPrimes(int n) { if (n <= 2) return 0; set myset;//存放非素数 myset.insert(1); for (int i = 2; i < n; i++) { if (myset.find(i) != myset.end()) continue; if (!isPrimes(i))//如果不是一个素数 { insertUnPrimesToSet(myset, i, n,0); } else//如果是一个素数 { insertUnPrimesToSet(myset, i, n, 1); } } return n -1 - myset.size() ; }
2016-08-13 16:06:04
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。