Python实现质数求和

入门级简单案例

Python的学习,在理论知识之外,通过实验项目练手是很有效的方式。本文以入门问题质数求和为例,希望对大家有所帮助。

思路说明

求解这个问题思路分为:分析算法和代码实现两个部分。

分析算法

质数的定义是大于1的自然数中,除了1和它本身以外不再有其他因数的数称为质数。最直接的算法是通过该数字和比自己小的数字取模看余数即可,把质数都找出来之后再进行求和。从数学上来说,求解质数有更优的方法,比如不需要把所有的数字取模,仅需要算1到该数的平方根以内的数即可等等。

代码实现

代码实现的方法一般是循环法或者向量法。循环法最常用,最近在学习Numpy库的使用,所以列出了利用矩阵、向量法和混合使用的案例。实验中,建议优先考虑实现目的,可以用一些固定的数字尝试,然后优化代码,封装函数,将功能变通用,让自己的代码变得简洁美观。别忘了最后多做几次测试,保证代码的正确性。最后,可以尝试计算代码的效率,初步有这样一个概念即可。

循环方法

基础办法

先判断任意数字x是否是质数,然后进行求和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# x = int(raw_input(prompt='please insert a number'))
x = 100
is_prime=0
for i in range(2,x):
if x % i == 0:
is_prime = 0
break
else:
is_prime = 1
if is_prime==0:
print "%d is not a prime" %x
if is_prime==1:
print "%d is a prime" %x

设置外层循环,对判断出来是质数的结果求和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# x = int(raw_input(prompt='please insert a number'))
x = 100
is_prime=0
sum=0
for j in range(2,x):
for i in range(2,j):
if j % i == 0:
is_prime = 0
break
else:
is_prime = 1
sum += j
print sum

利用数学知识

在上面的方法基础上,定义函数进行封装,另外,并不需要对每一个数字取模,只要保证平方根以内的整数计算即可。

1
2
3
4
5
6
7
8
9
10
def is_prime(x):
for i in range(2,int(x**(1/2.)+1)):
if x % i == 0:
is_prime_flag = 0
# print "it is not a prime"
break
else:
is_prime_flag = 1
# print "it is a prime"
return is_prime_flag

上面计算单个数字,下面进行求和,也是封装为函数。

1
2
3
4
5
6
def prime_sum(num):
sum = 0
for sum_i in range (2,num):
if is_prime(sum_i):
sum += sum_i
return sum

Numpy库实现

不用任何循环的方法如下,通过构建行列的数组,利用Numpy的广播特性取模后,得到了每一次计算的结果,利用特征值,通过np.where筛选出质数求和。

1
2
3
4
5
6
7
8
9
def is_prime_v(x):
a = np.arange(1,x+1)
b = a.reshape(x,1)
c = a % b
d = np.where(c>0,0,1)
e = d.sum(axis = 0)
f = np.where(e!=2,0,1)
g = (f*a).sum()
return g

向量方法

该方法借用了对单个数字是否为质数的判断,利用向量函数求出结果。参考Numpy 求100以内质数和

1
2
3
4
5
6
7
8
9
10
11
def judge_prime(x):
for i in range(2,int(x**(1/2.)+1)):
if x % i == 0:
is_prime_flag = 0
return False
return True
def sum_prime_v(y):
arr = np.arange(1,y+1)
v = np.vectorize(judge_prime)
return arr[v(arr)].sum()

代码说明

为了界面友好,可以利用raw_input函数提示输入,在该文中出现的函数和方法的说明参见另一篇文章。

效率比对

利用ipython的魔法函数计算执行效率:

1
%%timeit -n100

函数 10求和 100求和 1000求和 10000求和(取10次计算)
方法1:每个数取模循环 10.3 µs 295 µs 21 ms 1.73 s
方法2:平方根取模循环 16.8 µs 217 µs 2.68 ms 44.6 ms
方法3:Numpy构建数组 34.8 µs 222 µs 22.7 ms 2.65 s
方法4:向量函数计算 107 µs 238 µs 2.55 ms 40.8 ms

可以看出,利用平方根计算的方法最快,减少了大量的计算工作,在数字越大时越明显。基于平方根计算的向量方法在数字越大时效果更优。涉及到全部循环活着纯粹的矩阵构建因为每一次都要全部计算,效率比起来要差很多,在大数字计算时更为明显。

彩蛋

写代码就是玩游戏,要有一些惊喜才好玩。

  • 如果你执行了代码或者下面的源码会发现一些小错误。这些小错误是在笔者学习实践中产生的问题,因为这个问题有趣又入门,查找问题并不会花费太多时间,所以留给大家探索了。特别是向量化的方式计算的结果总是和另外几个结果不一样,你能找到原因并修复么?如果有困难,欢迎在github或者本文留言讨论。
  • 下面是源码地址,方便大家直接调用,不了解打开工具?Jupyter Notebook基本操作介绍已经详细说明。
  • 代码本身并不重要,代码背后的探索过程以及大量内隐知识才是真正的财富。这部分内容自己会尽量的根据学习经验总结,教会你,也教会N天前的自己学Python与数据分析。如果你有更好的意见和建议,欢迎留言,大家一起玩。
  • 感谢数据科学班带来的有趣的题目,本文借鉴了同学们大量作业的思路,一并感谢。

声明: 本文转载需标明出处,禁止用于商业目的。

ChangeLog

161201 新建
160203 发布