首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

素数

prime number

质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。与之相对的是合数,指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数,1既不属于质数也不属于合数。

在密码学中,公钥即就是将传递的信息编码时加入质数,则解密的过程中(实为寻找素数的过程)。

在汽车变速器的设计上,相邻的两个大小齿轮齿数设计成质数,可增强耐用度减少故障。

以质数形式无规律变化的导弹可以使敌人不易拦截。

由此可见质数非常有用,在程序中有关质数的考量也有很多方式,一起来看看吧。

1. 二进制表达式中质数

题目:

给定两个整数L和R,找到在[L, R]范围内二进制表达式中设置位计数为素数的个数。整数的设置位是以二进制中1的数量。例如,21的二进制为10101,其中设置位个数为3。

例1:

输入:L=6,R=10

输出: 4

说明:

6 -> 110(2位)

7 -> 111(2位)

9 ->1001(2位)

10 ->1010(2位)

其中,L,R是[1,10^6]范围内的整数L

分析

这一题可以分解成三个步骤,首先将十进制数转成二进制数,其次,计算二进制数中置位为1的个数,最后判断是否为素数即可。由于L,R最大值为10^6,小于2的20次方,提前计算20以内中的素数。

python 代码:

class Solution(object):

def countPrimeSetBits(self, L, R):

"""

:type L: int

:type R: int

:rtype: int

"""

prime_dict = {

1: False,

2: True,

3: True,

4: False,

5: True,

6: False,

7: True,

8: False,

9: False,

10: False,

11: True,

12: False,

13: True,

14: False,

15: False,

16: False,

17: True,

18: False,

19: True,

20: False,

}

return len([i for i in xrange(L, R+1) ifprime_dict[bin(i).count("1")]])

2. 素数个数

题目:

计算小于非负整数n的素数个数。

例1:

输入: 10

输出: 4

说明:

小于10的素数有4个,分别是2,3,5,7.

分析

一般方法是找出所有小于n的素数,计算总数即可,需要n^2的时间复杂度,而且判断素数的过程中需要使用除法,需要大量计算,是一个较差的方式,那如何计算出素数个数呢?可以使用埃拉托斯特尼筛法。通过逐个排除非素数,比如2为素数,2*2=4,2*3=6,2*4=8...都是非素数,接着轮询3,3*2=6,3*3=9,3*4=12...等等,每次都排除一部分,逐个寻找下一个素数即可。

python 代码:

class Solution(object):

def countPrimes(self, n):

"""

:type n: int

:rtype: int

"""

if n

bit = [1]*n

bit[0] = bit[1] = 0

i = 2

half = n/2+1

while i

p = 2*i

while p

bit[p] = 0

p += i

i += 1

return sum(bit)

提前给大家拜年啦,祝大家新春愉快,身体健康,万事如意。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190130G0EDO800?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券