本文主要是介绍算法---计数质数(Java)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：计数质数
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
提示：
0 <= n <= 5 * 106
解决方法：(埃氏筛)
思路：
算法由希腊数学家厄拉多塞（\rm EratosthenesEratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。
我们考虑这样一个事实：如果 xx 是质数，那么大于 xx 的 xx 的倍数 2x,3x,\ldots2x,3x,… 一定不是质数，因此我们可以从这里入手。
public int countPrimes2(int n){//create cacheint[] ints = new int[n];//fill 1Arrays.fill(ints,1);//for 2...nint result = 0;for (int i = 2;i < n;i ++){//if cache[i] == 1 set i*i = 0 then i=i*i+iif (ints[i] == 1){//System.out.println(i);result++;//负数会搞乱质数的工作进程 因为会发生 j += iif ((long)i * i < n) {for (int j = i * i; j < n; j += i) {ints[j] = 0;}}}}return result;}
参考：
https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-by-leetcode-solution/
这篇关于算法---计数质数(Java)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
