題目描述
統計所有小于非負整數 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

總結

以上是生活随笔為你收集整理的计数质数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。