1.判断素数
1.什么是素数
因数是指整数a除以整数b(b≠0) 的商正好是整数而没有余数，我们就说b是a的因数
例如：16÷2=8，在这个例子当中，没有余数产生，因此2就是16的因数
素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数
例如：2,3,5,7,11,13都是素数
2.判断素数
知道了什么素数之后，我们就可以开始分析如何用程序的方式去判断素数了，我们先来看几个例子
在这个例子当中
对于数字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("是素数")
运行结果：
结果与我们预想的一样，对于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)
运行结果：
代码非常简单，但有一个地方需要解释，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)运行结果：
3.return的使用
实际上，return除了可以作为返回来使用以外，还可以用于终止函数的运行，比如下面这个例子
def function_one():
for i in range(5):
if i==2:
return
print(i)
function_one()运行结果如下：
有了这个之后，我们就可以对我们上面的素数算法进行优化了，由于我们是按照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)运行结果如下：
注意：在这个代码中，我们用的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)运行结果如下：
我们使用了start=time.time()和end=time.time()来记录开始和结束的时间，最后打印它们之间的差值，即可得到最后的运行时间，并且把判断范围改成2~5000，这个程序的运行时间是0.29秒，
我们可以试试没有用return的算法，看看运行时间：
我们可以发现，大大的节约了运行时间
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)我们来看看这次的运行时间：
时间再一次大大的缩减
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))运行结果：
