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)
提前给大家拜年啦,祝大家新春愉快,身体健康,万事如意。
领取专属 10元无门槛券
私享最新 技术干货