LeetCode——计数质数

xiaoxiao2021-02-28  5

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

思路:大于2的偶数都不是质数,所以我们只需要判断奇数是不是质数。

代码如下:

public int CountPrimes(int n) { if(n<3) return 0; int count=n/2; bool[] f=new bool[n]; for(int i=3;i*i<=n;i+=2) { if(f[i]) continue; for(int j=i*i;j<n;j+=2*i) { if(!f[j]) { --count; f[j]=true; } } } return count; }
转载请注明原文地址: https://www.6miu.com/read-1600020.html

最新回复(0)