计数质数

我会带着你远行 2022-02-25 06:10 213阅读 0赞

**题目描述**  
统计所有小于非负整数 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]的倍数，均置为0
            		for(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][https_blog.csdn.net_gavinming_article_details_7212980]

[https_blog.csdn.net_gavinming_article_details_7212980]: https://blog.csdn.net/gavinming/article/details/7212980

发表评论取消回复

表情：

评论列表（有 0 条评论，213人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode204-计数质数

文章目录计数质数题目描述 code 计数质数题目描述统计所有小于非负整数 n 的质数的数量。示例: 输

落日映苍穹つ/ 2023年05月29日 06:53/ 0 赞/ 159 阅读

相关 11-07 计数质数

[原题链接][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6

旧城等待，/ 2022年12月19日 11:50/ 0 赞/ 55 阅读

相关 LeetCode204——计数质数

统计所有小于非负整数 n 的质数的数量。示例 1：输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

ゞ浴缸里的玫瑰/ 2022年11月15日 12:57/ 0 赞/ 136 阅读

相关 leetcode 204. 计数质数

[leetcode链接][leetcode] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_

￡神魔★判官ぃ/ 2022年09月03日 02:29/ 0 赞/ 177 阅读

相关 leetcode 204. 计数质数

统计所有小于非负整数 n 的质数的数量。示例: 输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7

谁借莪１个温暖的怀抱￠/ 2022年05月17日 23:23/ 0 赞/ 163 阅读

相关 [LeetCode] 计数质数

出处 > [计数质数][Link 1] 分析方法1: 该题若采用循环方式从1 ~ n 判断每一个是否是质数，其中判断质数又直接循环3 ~ m 是否能被整

超、凢脫俗/ 2022年05月17日 06:27/ 0 赞/ 135 阅读

相关【LeetCode】204. 计数质数

题目链接：[https://leetcode-cn.com/problems/count-primes/description/][https_leetcode-cn.com_

谁践踏了优雅/ 2022年04月21日 23:22/ 0 赞/ 185 阅读

相关计数质数

题目描述统计所有小于非负整数 n 的质数的数量。示例: 输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2,

我会带着你远行/ 2022年02月25日 06:10/ 0 赞/ 214 阅读

相关 LeetCode: 204. 计数质数

题目描述: 统计所有小于非负整数 n 的质数的数量。示例: 输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个,

╰半橙微兮°/ 2021年12月03日 13:27/ 0 赞/ 270 阅读

相关 LeetCode-计数质数

描述：统计所有小于非负整数n的质数的数量。示例：输入：10；输出：4；解释：小于10的质数一共有4个，它们是2,3,5,7。解题思路： 1、暴力破解验证一

迷南。/ 2021年09月23日 14:32/ 0 赞/ 269 阅读