素数

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)

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