如何做论坛网站 知乎,公司网站建设多少费用,怀柔建设网站公司,门户网站系统架构目录 题目描述:示例 1#xff1a;示例 2#xff1a;代码实现#xff1a; 题目描述:
给定整数 n #xff0c;返回 所有小于非负整数 n 的质数的数量 。
示例 1#xff1a;
输入#xff1a;n 10 输出#xff1a;4 解释#xff1a;小于 10 的质数一共有 4 个, 它们是 … 目录 题目描述:示例 1示例 2代码实现 题目描述:
给定整数 n 返回 所有小于非负整数 n 的质数的数量 。
示例 1
输入n 10 输出4 解释小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2
输入n 0 输出0
代码实现
class Solution {public int countPrimes(int n) {int[] isPrime new int[n];// 标记n以内的质数1为合数0为质数int count 0;// 质数个数for (int i 2; i n; i) {// 从2开始遍历if (isPrime[i] 0) {count;// 质数个数加一if ((long) i * i n) {// 将 i 转换为 long 的原因是为了防止乘法溢出导致错误的结果for (int j i * i; j n; j i) {// 如果i是质数那么i的倍数一定不是质数isPrime[j] 1;// 标记为合数}}}}return count;// 返回个数}
}
