素数算法

1.判断素数

1.什么是素数

因数是指整数a除以整数b(b≠0) 的商正好是整数而没有余数,我们就说b是a的因数
例如:16÷2=8,在这个例子当中,没有余数产生,因此2就是16的因数

素数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数
例如:2,3,5,7,11,13都是素数

2.判断素数

知道了什么素数之后,我们就可以开始分析如何用程序的方式去判断素数了,我们先来看几个例子

image-20201013165359153
在这个例子当中
对于数字2:1是因数 2是因数 总共有2个因数
对于数字3: 1是因数 2不是因数 3是因数 总共有2个因数
对于数字4: 1是因数 2是因数 3不是因数 4是因数 总共有3个因数

因此,我们可以发现2和3只有两个因数,但是4有3个因数,因此,2,3是素数,而4不是素数

在这个例子当中,对于数字N来说,我们是通过判断1,2,3,……,N 是不是N的因数来判断N是不是素数,只要因数的个数大于2那我们就说它不是一个素数,相反,则是一个素数

因此对于数字N来说,我们可以使用range(1,N+1)来产生这个序列,并让N分别整除这个序列中的每一个数字,如果产生的余数为0,那说明这个数字是N的一个因数,经过这个思路,我们就可以很容易的写出程序

number=15       #要判断的数
n=0             #记录因数的个数

for i in range(1,number+1):
    if number%i==0:
        n+=1

if n>2:
    print("不是素数")
else:
    print("是素数")

运行结果:

image-20201013170951167

结果与我们预想的一样,对于15来说,分别有4个因数,1、3、5、15,因此15不是一个素数

2.统计素数的个数

刚才我们只是判断一个特定的数字是不是素数,现在,我们有一个新的需求:我们想要知道2-100有哪些数字是素数,这个问题,我们应该如何去解决呢?

实际上,我们可以将刚才的功能定义为一个函数,方便我们进行调用,比如:

def prime(x):
    number=x        #要判断的数
    n=0             #记录因数的个数

    for i in range(1,number+1):
        if number%i==0:
            n+=1

    if n>2:
        return False
    else:
        return True

我们将刚才的代码功能,打包成一个函数,接下来,要判断2-100那些数是素数,我们只需要调用这个函数就可以了

def prime(x):
    number=x        #要判断的数
    n=0             #记录因数的个数

    for i in range(1,number+1):
        if number%i==0:
            n+=1

    if n>2:
        return False
    else:
        return True

list_prime=[]       #定义空列表,用于存储素数

#逐个进行判断
for i in range(2,101):
    if prime(i):
        list_prime.append(i)

#打印结果
print(list_prime)

运行结果:

image-20201013172605573

代码非常简单,但有一个地方需要解释,return表示返回一个结果,什么叫返回呢?在我们以前的使用中,比如pen=turtle.Pen(),在这个代码中turtle.Pen()这个函数产生了一个结果,也就是一支笔,并把这支笔通过赋值号给了变量pen,这就是一个返回的过程

在我们这个程序当中,prime(x)这个函数,返回了一个布尔值因此,我们可以用一个变量来存储这个布尔值,比如使用result=prime(3),由于3是一个素数,因此result的结果应该是True

def prime(x):
    number=x        #要判断的数
    n=0             #记录因数的个数

    for i in range(1,number+1):
        if number%i==0:
            n+=1

    if n>2:
        return False
    else:
        return True

result=prime(3)
print(result)

运行结果:

image-20201013173240136

3.return的使用

实际上,return除了可以作为返回来使用以外,还可以用于终止函数的运行,比如下面这个例子

def function_one():
    for i in range(5):
        if i==2:
            return
        print(i)
function_one()

运行结果如下:

image-20201014144325097

有了这个之后,我们就可以对我们上面的素数算法进行优化了,由于我们是按照1~N的方式进行逐个测试,而对于任何自然数来说,1和它本身都是它的因数,因此,如果我们再2~N-1中只要找到一个是N的因数,那就说明N不是素数,我们就没有必要在对它进行计算了,比如对于数字9来说,1是它的因数,2不是因数,3是它的因数,我们发现3是它的因数之后,就能够判断它不是素数,而没有必要在浪费资源判断4-9了,提高了运算速度

改进代码如下:

def prime(x):
    number=x        #要判断的数
    n=0             #记录因数的个数

    for i in range(2,number):
        if number%i==0:
            return False
    return True

list_prime=[]       #定义空列表,用于存储素数

#逐个进行判断
for i in range(2,101):
    if prime(i):
        list_prime.append(i)

#打印结果
print(list_prime)

运行结果如下:

image-20201014151727203

注意:在这个代码中,我们用的range(2,numer)而不range(1,numer+1),由于1和N本身一定是因数,因此我们取消掉这两个数不进行判断

4.time库计算运行时间

虽然经过刚才的优化,从理论上来说,我们的确减少了程序的运行时间,但是如何去直观的看到程序到底运行了多久呢?因此,我们需要使用一个工具——time库,来看看这个程序到底需要花多久的时间去完成

import time         #导入time库

start=time.time()   #记录开始时间

def prime(x):
    number=x        #要判断的数
    n=0             #记录因数的个数

    for i in range(2,number):
        if number%i==0:
            return False
    return True

list_prime=[]       #定义空列表,用于存储素数

#逐个进行判断
for i in range(2,5000):
    if prime(i):
        list_prime.append(i)

#打印结果
print(len(list_prime))

end=time.time()     #记录结束时间

print("time:",end-start)

运行结果如下:

image-20201014151804725

我们使用了start=time.time()end=time.time()来记录开始和结束的时间,最后打印它们之间的差值,即可得到最后的运行时间,并且把判断范围改成2~5000,这个程序的运行时间是0.29秒,

我们可以试试没有用return的算法,看看运行时间:

image-20201014151433968

我们可以发现,大大的节约了运行时间

5.程序优化

实际上,我们还可以对程序进一步优化,对于数字8来说,我们实际上只需要测试2~4就可以了,因为5~7必然会产生小数,所以5~7必然不会是它的因数,我们就没有必要在对它们进行测试了,

因此,对于一个数字N来说,我们只需要测试2~N/2的范围就可以了,减少循环次数

import time         #导入time库

start=time.time()   #记录开始时间

def prime(x):
    number=x        #要判断的数
    n=0             #记录因数的个数

    for i in range(2,number//2+1):
        if number%i==0:
            return False
    return True

list_prime=[]       #定义空列表,用于存储素数

#逐个进行判断
for i in range(2,5000):
    if prime(i):
        list_prime.append(i)

#打印结果
print(len(list_prime))

end=time.time()     #记录结束时间

print("time:",end-start)

我们来看看这次的运行时间:

image-20201014152229616

时间再一次大大的缩减

6.综合练习

1.编写程序判断2到100的合数以及统计其个数。

合数:合数可以有多个约数,一般表示除了1和它本身之外还有其他约数的自然数,都称为合数

def composite(x):
    number=x        #要判断的数
    n=0             #记录因数的个数

    for i in range(2,number//2+1):
        if number%i==0:
            return True
    return Flase

list_composite=[]       #定义空列表,用于存储合数

#逐个进行判断
for i in range(2,101):
    if composite(i):
        list_composite.append(i)

#打印结果
print(list_composite)
print("number:",len(list_composite))

运行结果:

image-20201014152813713

© 版权声明
THE END
喜欢就支持以下吧
点赞9
分享
评论 抢沙发
四曲的头像-四曲博客

昵称

取消
昵称表情代码图片