leetcode 204. Count Primes 这道题很有趣 + 搜索空间递减

拼搏现实的明天。 2022-06-08 09:13 110阅读 0赞

Description:

Count the number of prime numbers less than a non-negative number, n.

这道题就是考察小于n的所有的质数的数量，直接遍历肯定超时，所以使用布尔数组来筛掉不符合条件的数字，该数字就不再进入下一层循环进行判断了。

代码如下：

import java.util.Arrays;
    
    public class Solution 
    {
        
        //http://blog.csdn.net/criminalcode/article/details/68954073
        public int countPrimes(int n) 
        {
            boolean[] vis= new boolean[n];
            Arrays.fill(vis,false);
            int cnt=0;
            for(int i=2;i<n;i++)
            {
                if(vis[i]==false)
                {
                    cnt++;
                    for(int j=2;j*i<n;j++)
                        vis[i*j]=true;              
                }
            }
            return cnt;
        }
    }

下面是C++的做法，使用数组做一次搜索空间递减，很棒的想法

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    #include <map>
    #include <set>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <algorithm>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int countPrimes(int n)
        {
            vector<bool> flag(n, false);
            int count = 0;
            for (int i = 2; i < n; i++)
            {
                if (flag[i] == false)
                {
                    count++;
                    for (int j = 2; j*i < n; j++)
                        flag[j*i] = true;
                }
            }
            return count;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode - Easy - 204. Count Primes

Topic Hash Table Math Description [https://leetcode.com/problems/count-prim

不念不忘少年蓝@/ 2022年12月31日 01:14/ 0 赞/ 79 阅读

相关 LeetCode:204. Count Primes计数质数(C语言)

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

布满荆棘的人生/ 2022年12月26日 04:52/ 0 赞/ 85 阅读

相关 leetcode 204/187/205 Count Primes/Repeated DNA Sequences/Isomorphic Strings

一：leetcode 204 [Count Primes][] 题目： Description: Count the number of prime numbers le

今天药忘吃喽~/ 2022年08月08日 05:27/ 0 赞/ 123 阅读

相关 Count Primes （质数的个数）

Description: Count the number of prime numbers less than a non-negative number, n. Hin

小灰灰/ 2022年07月15日 01:22/ 0 赞/ 171 阅读

相关 LeetCode204—Count Primes

原题 [原题链接][Link 1] > Description: > > Count the number of prime numbers less than a

痛定思痛。/ 2022年07月13日 09:50/ 0 赞/ 141 阅读

相关 [leetcode]: 204. Count Primes

1.题目 Description: Count the number of prime numbers less than a non-negative number,

痛定思痛。/ 2022年06月14日 09:55/ 0 赞/ 121 阅读

相关 leetcode 204. Count Primes 这道题很有趣 + 搜索空间递减

Description: Count the number of prime numbers less than a non-negative number, n. 这道题

拼搏现实的明天。/ 2022年06月08日 09:13/ 0 赞/ 111 阅读

相关（Java）leetcode-204 Count Primes

【统计质数】 Count the number of prime numbers less than a non-negative number, n. Example:

谁借莪１个温暖的怀抱￠/ 2022年04月24日 13:54/ 0 赞/ 146 阅读

相关 LeetCode 204.Count Primes (计数质数)

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

叁歲伎倆/ 2022年04月15日 01:13/ 0 赞/ 190 阅读

相关几道有趣的算法题

　　题目：给定一个数字，得出这个数字的连续正整数之和，如给出15，得出1+2+3+4+5=4+5+6=7+8 1 public

约定不等于承诺〃/ 2021年12月05日 03:53/ 0 赞/ 242 阅读