欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode刷题记录-204. Count Primes

程序员文章站 2022-04-25 15:19:57
...

leetcode刷题记录-204. Count Primes

1.题目要求

  Description:
  Count the number of prime numbers less than a non-negative number, n.
  就是给定一个非负整数n,找出小于n的质数的个数


2.问题分析

  质数(也叫素数)的定义:大于等于2,且只能被1和自己整除


3.解题思路

  • 思路一
      对于范围【1,n)的每个数,依次从1开始遍历,统计整除的次数,如果次数为2,说明是质数,从而统计出来小于n的质数的个数。
      代码如下:
int countPrimes(int n)
{
    int i, cnt, output = 0;
    while (n >= 2)
    {
        n--;
        cnt = 0;
        for (i = 1; i <= n; i++)
        {
            if (n%i == 0)
                cnt++;
        }
        if (cnt == 2)
            output++;

    }
    return output;
}

  提交的时候报错,时间复杂度太高,输入的n越大,那么耗时越长。。。所以不可取。在此基础上稍微改进,见思路二

  • 思路二
      查找有关判断一个数是否为质数的方法,看到篇博客,写的很好
      https://blog.csdn.net/huang_miao_xin/article/details/51331710,里面提到了要判断一个数是否为质数,其实并不需要从1判断到n,因为一个数若可以进行因数分解,那么分解时得到的两个数一定是一个小于等于sqrt(n),一个大于等于sqrt(n)。所以只需要遍历到sqrt(n)即可,
      实现代码如下:
int countPrimes(int n)
{
    int i, cnt=0, output = 0;
    int n_sqrt;
    if (n == 2)
        output = -1;
    while (n >= 2)
    {
        n--;
        n_sqrt = sqrt(n)+1;
        cnt = 0;
        for (i = 2; i <= n_sqrt; i++)
        {
            if (n%i == 0)
                cnt++;
        }
        if (cnt == 0)
            output++;
    }
    return output;
}

  这种方法的效率仍然比较低,上面的博客里面还提到了第三种方法也很巧妙,这里不详述。


  • 思路三
      上面两个代码都不通过。。。心很累。于是向讨论区大神求助,果然找到了好的方法,先贴代码:
      
int countPrimes(int n)
{
    vector<bool> prime(n, true);
    prime[0] = prime[1] = false;
    int i,j;
    for (i = 0; i < sqrt(n); i++)
    {
        if (prime[i])
        {
            for (j = i*i; j < n; j += i)
                prime[j] = false;
        }
    }
    return count(prime.begin(), prime.end(),true);
}

  乍一看确实不怎么好懂,可以参考*上的解释,讲的很详细,链接在这里:https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes,示意图如下:
leetcode刷题记录-204. Count Primes
  这种思路就是用这种方法实现的,时间复杂度也很低。需要注意的是j一定不能从i开始(不然就会把i自身给排除掉),然后每次递增i,这样就会把所有不是质数的数字都遍历到,剩下的就全是质数啦!
  注:如果严格按照*上的来的话,for循环里面应该是
  (j=2*i;j<n;j+=i),改成从i*i开始则进一步减小了时间复杂度,而且效果是一样的.
  

相关标签: cpp