阿里巴巴网站维护要怎么做,营销型门户网站,vs做网站用3层架构,中文编程题目描述 统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。解法 思路1#xff1a;暴力法
/***暴力法* 时间复杂度O(n2)* 空间复杂度(O(1))* param n* return*/
public int countPrimes(int n) {if(n暴力法
/***暴力法* 时间复杂度O(n2)* 空间复杂度(O(1))* param n* return*/
public int countPrimes(int n) {if(n0) {return 0;}int count 0;for(int i2;in;i) {int j 2;for(;ji;j) {if(i%j 0) {break;}}if(j i) {count;}}return count;}/*** 厄拉多塞筛法* 时间复杂度O(n2)* 空间复杂度(O(1))* param n* return*/public int countPrimes(int n) {if(n1) {return 0;}int[] arr new int[n-2];for(int i0;in-2;i) {arr[i] i2;}for(int i0;iarr.length;i) {if(arr[i] ! 0) {//后续所有arr[i]的倍数均置为0for(int times 2;arr[i] *timesarr.length2;times) {arr[arr[i] *times-2] 0;}}}int count0;for(int num:arr) {if(num !0) {count;}}return count;}解法参考 https://blog.csdn.net/gavinming/article/details/7212980
