Python实现质数求和

Posted on | Edited on | In |
入门级简单案例

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 发布