leetcode-204-Count Primes

题目描述:

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

要完成的函数:

int countPrimes(int n) 

说明:

1、题目看上去非常简单和熟悉。给定一个非负数n,要求返回小于n的所有素数的个数。

2、处理一下边界条件,n<=2时返回0,n=3时返回1,n=4时返回2。

3、传统方法:

对于小于n的每个数i,判断i是不是素数。判断方法是对于每个大于等于2且小于等于i/2的数,确定i能否整除这个数。

双重循环,暴力解法。然后在这道题中超时了。

代码如下:

bool prime(int i)
    {
        for(int j=2;j<=i/2;j++)//小循环
        {
            if(i%j==0)
                return false;
        }
        return true;
    }
    int countPrimes(int n) {
        int count=0;
        if(n<=2)
            return count;
        else if(n==3)
            return 1;
        else if(n==4)
            return 2;
        count=2;
        for(int i=4;i<n;i++)//大循环
        {
            if(prime(i))
                count++;
        }
        return count;
    }

4、改进1:

我们尝试做一些改进,比如在大循环中,能不能只判断奇数,毕竟偶数都不是素数,没有必要判断,这样可以省很多时间。

此外,在小循环中,能不能控制j为奇数,毕竟大循环中的要判断的奇数,只会由另外两个奇数相乘而得到。

还有,我们可以把小循环中的判断条件:i/2,改成sqrt(i)。这个也能省不少时间。

我们来试一下:

    bool prime(int i)
    {
        for(int j=3;j<=sqrt(i);j+=2)//j每次都+2
        {
            if(i%j==0)
                return false;
        }
        return true;
    }
    int countPrimes(int n) {
        if(n<=2)//这次要判断的边界条件比较多,相信看完一整个代码的你会理解的
            return 0;
        else if(n==3)
            return 1;
        else if(n==4||n==5)
            return 2;
        else if(n==6||n==7)
            return 3;
        else if(n==8)
            return 4;
        int count=4;
        for(int i=9;i<=n;i+=2)//从i=9开始判断,只对奇数进行判断
        {
            if(prime(i))
                count++;
            if(i==n&&prime(n))//如果n是一个奇数和素数,那么count要减去1;如果n是奇数和非素数,那么不用减
                  //去1,因为上一行代码在最后没有执行到。
                count--;    //如果n是一个偶数,那更加不用减去1。
        }
        return count;
    }

这次代码通过测试,beats 7.36% of cpp submissions,实测452ms。

5、改进2:

我们能否再做一些改进?

上述代码浪费时间的地方在于:

比如我们要判断19*31=589是不是素数,那么我们要对589%9做出判断,对589%11做出判断,对589%13做出判断,对589%15做出判断,对589%19做出判断。

然后我们对于下一个数19*41=779判断是否素数,要对779%9做出判断,对779%11做出判断,对779%13做出判断,对779%15做出判断,对779%19做出判断。

我们浪费了很多时间在不停地判断上面。我们可不可以用素数相乘的方式,直接生成一些合数,然后不断地筛掉它们。这样可以避免花费大量时间在判断上面。

代码如下:

int countPrimes(int n) 
{
    if (n<=2) 
        return 0;
    vector<bool> prime(n, false);//定义一个长度为n,初始为false的bool型vector容器
    int sum = 1;
    int upper = sqrt(n);
    for (int i=3; i<n; i+=2) //对每个奇数进行处理
    {
        if (!prime[i]) //初始i=3,是一个质数,进入后续处理。之后每次都判断是不是质数,如果是就进行处理。
        {
            sum++;
            if (i>upper) 
                continue;
            for (int j=i*i; j<n; j+=2*i) //比如3*3=9,9就是一个合数。然后9+3*2=15=i*i+2i,也是一个合
       {                  //数。后续不断循环处理。这里最好是处理成j+=2*i,而不是j+=i,
                              //思考一下原因?评论区有答案~这个细节可以省一半时间。
                prime[j] = true;
            }
        }
    }
    return sum;
}

最终实测16ms,beats 97% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏天天

Airbnb JavaScript Style Guide

const foo = 1; let bar = foo; bar = 9; console.log(foo, bar); // => 1, 9

1722
来自专栏尾尾部落

[剑指offer] 不用加减乘除做加法

872
来自专栏极乐技术社区

使用ES6新特性开发微信小程序(1)

ECMAScript 6(简称ES6)是JavaScript语言的最新标准。因为当前版本的ES6是在2015年发布的,所以又称ECMAScript 2015。 ...

2185
来自专栏数据结构与算法

177. [USACO Jan07] 有限制的素数

177. [USACO Jan07] ★   输入文件:qprime.in   输出文件:qprime.out   简单对比 时间限制:1 s   内存限制:...

3649
来自专栏C/C++基础

不用加号实现两整数相加

对于二进制的加法运算,若不考虑进位,则1+1=0,1+0=1,0+1=1,0+0=0,通过对比异或,不难发现,此方法与异或运算类似。因而排出进位,加法可用异或来...

592
来自专栏小筱月

javascript sort 函数用法

简单的说,sort() 在没有参数时,返回的结果是按升序来排列的。即字符串的Unicode码位点(code point)排序

1523
来自专栏swag code

swap()交换两个变量的方法汇总

1014
来自专栏java达人

js的回调函数详解

在Javascript中,函数是第一类对象,这意味着函数可以像对象一样按照第一类管理被使用。既然函数实际上是对象:它们能被“存储”在变量中,能作为函数参数被传递...

3325
来自专栏菩提树下的杨过

Flash/Flex学习笔记(8):ActionScript3.0中的面对对象

首先要习惯AS3.0的几个BT约定: 1.一个.as文件中,只能定义一个类 2.类名称必须与.as的文件名相同 3.类定义中必须要有package包声明 4.一...

1789
来自专栏韦弦的偶尔分享

Swift 计数质数 - LeetCode

2053

扫码关注云+社区

领取腾讯云代金券