计数质数

题目描述
统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

解法
思路1：暴力法

/***暴力法* 时间复杂度O(n`2)* 空间复杂度(O(1))* @param n* @return*/ public int countPrimes(int n) {if(n<=0) {return 0;}int count =0;for(int i=2;i<n;i++) {int j =2;for(;j<i;j++) {if(i%j ==0) {break;}}if(j == i) {count++;}}return count;} /*** 厄拉多塞筛法* 时间复杂度O(n`2)* 空间复杂度(O(1))* @param n* @return*/public int countPrimes(int n) {if(n<=1) {return 0;}int[] arr = new int[n-2];for(int i=0;i<n-2;i++) {arr[i] = i+2;}for(int i=0;i<arr.length;i++) {if(arr[i] != 0) {//后续所有arr[i]的倍数，均置为0for(int times =2;arr[i] *times<arr.length+2;times++) {arr[arr[i] *times-2] =0;}}}int count=0;for(int num:arr) {if(num !=0) {count++;}}return count;}

解法参考：
https://blog.csdn.net/gavinming/article/details/7212980

总结

以上是生活随笔为你收集整理的计数质数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。