Numpy 求100以内质数和

一百以内质数之和

判断是否为质数

判断一个整数是否为质数比较简单,即除了自身和1以外不可被别的数整除。不过根据数学理论证明,不用从2检查到n,到int(sqrt(n))+1即可,可以提高效率。注意返回值为True或False,方便后续的boolean索引。

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2,int(np.sqrt(num))+1):
        if num % i == 0:
            return False
    return True

利用循环

简单粗暴的方式,从1循环到100,一次判断是否为质数,若是质数,则加到ans上,若不是直接跳过。因为%%timeit会执行1000,所以跑完代码就comment out了。

def prime_sum_iter(n=100):
    ans = 0
    for i in range(1,n+1):
        if is_prime(i):
            ans += i
    return ans

print prime_sum_iter()
# %%timeit
# 1000 loops, best of 3: 253 µs per loop
1060

利用np向量化方法

利用numpy可以向量化,用更简洁的方式遍历所有的元素。向量化的理解,就本例子而言,循环的思想是每次取一个数,对其判断是否为质数;向量化是取这个数组为变量,直接对其所有元素判断是否为质数,然后返回一个同size的数组。由于is_prime()函数本身接受单个integer,如要接受向量、数组等变量,需要对函数进行向量话,is_prime_vec = np.vectorize(is_prime)。

np.vectorize: Define a vectorized function which takes a nested sequence of objects or numpy arrays as inputs and returns a numpy array as output,具体可参考文档

is_prime_vec(np_arr)返回一个布尔型数组,比如np_arr = array([1,2,3,4]);那is_prime_vec(np_arr)返回array([False, True, True, False]),因为2,3是质数,1,4不是。np_arr[is_prime_vec(np_arr)]是布尔索引,简单讲就是返回对应True的元素,这里会返回array([2,3]),因为2,3对应的boolean值为True。之后再sum就实现了和循环一样的功能。

def prime_sum_vect(n=100):
    np_arr = np.arange(1,n+1)
    is_prime_vec = np.vectorize(is_prime)
    return np.sum(np_arr[is_prime_vec(np_arr)])

print prime_sum_vect()
# %%timeit
# 1000 loops, best of 3: 286 µs per loop
1060

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

407. 加一加和进位分开处理

给定一个非负数,表示一个数字数组,在该数的基础上+1,返回一个新的数组。 该数字按照大小进行排列,最大的数在列表的最前面。 样例 给定 [1,2,3] 表...

791
来自专栏轮子工厂

一口气吃下数组的存储方式

Long long ago,我们讲到了数组《聊一聊数组背后的那点事》,这个已经是迈进指针的第一步了,主要的内容是一维数组,今天我们将讲述二维数组。当结束了今天的...

1091
来自专栏Python爬虫实战

numpy基础操作快速入门

由于numpy不是python自带库,需要自己下载安装(如果用的是Anaconda,则不需要再去下载numpy库,因为其自带python环境以及许多第三方pyt...

641
来自专栏武培轩的专栏

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法...

3294
来自专栏和蔼的张星的图像处理专栏

488. 快乐数

一个数是不是快乐是这么定义的:对于一个正整数,每一次将该数替换为他每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,或是无限循环但始终变不到1。如果可...

1423
来自专栏黑泽君的专栏

java基础学习_基础语法(下)02_day06总结

============================================================================= ==...

551
来自专栏Python小屋

Python版堆排序算法

其他排序算法的Python实现请参考:Python版归并排序算法(附Python程序__name__属性用法演示视频),侏儒排序算法原理与Python实现,Py...

2975
来自专栏静默虚空的博客

排序一 冒泡排序

要点 冒泡排序是一种交换排序。 什么是交换排序呢? 交换排序:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止。 算法思想 它...

2085
来自专栏尾尾部落

[LeetCode]Merge Sorted Array 合并排序数组 [LeetCode]Merge Sorted Array 合并排序数组

链接:https://leetcode.com/problems/merge-sorted-array/description/ 难度:Easy 题目:88...

691
来自专栏前端儿

ASCII码排序

输入第一行输入一个数N,表示有N组测试数据。后面的N行输入多组数据,每组输入数据都是占一行,有三个字符组成,之间无空格。输出对于每组输入数据,输出一行,字符中间...

1682

扫码关注云+社区