专栏首页Python小屋最优的素数判断代码(Python)是这样写出来的

最优的素数判断代码(Python)是这样写出来的

素数判断是个很经典的问题,各种语言的程序设计课程都会涉及到,按照素数定义(除了1和自身,素数没有其他因数)很容易写出下面的代码:

def isPrime1(n):

for i in range(2, n):

if n%i == 0:

return False

return True

功能完全没有问题,就是非常非常非常非常慢。大家都明白,之所以那么慢是因为测试的范围实在是太大了,如何缩小范围呢,大家也是非常熟悉的:不需要测试从2到n-1这个完整的范围里有没有n的因数,只需要测试从2到n的平方根这个范围就可以了。假设m是n的平方根,如果2到m之间没有n的因数,那么m到n-1之间也必然没有n的因数。明白了道理之后,代码就好写了:

def isPrime2(n):

#与下面的截图稍微有一点点区别

m = int(n**0.5)+1

for i in range(2, m):

if n%i == 0:

return False

return True

可以想象,对于大整数来说,这样的改进是非常有意义的,具体能加速多少呢?看看下面的图就知道了:

太震撼了,速度确实提高很多,那么还能不能再进一步优化和提升呢?看下面的代码:

def isPrime3(n):

if n%2 == 0:

return False

#只判断奇数,范围缩小一半

for i in range(3, int(n**0.5)+1, 2):

if n%i == 0:

return False

return True

让我们再来比较一下速度:

perfect!

本文分享自微信公众号 - Python小屋(Python_xiaowu),作者:董付国

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-11-14

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python求解一元二次方程根

    本文使用Python实现一元二次方程求根公式,主要演示运算符和几个内置函数的用法,封面图片与本文内容无关。 def root(a, b, c, highmidd...

    Python小屋屋主
  • 针对递归函数的优化与Python修饰器实现

    我们围绕一个数学问题来说明本文的思想,组合数C(n,i),也就是从n个元素中任选i个,共有多少种选法。当然,这个问题有很多种求解方法,例如【最快的组合数算法之P...

    Python小屋屋主
  • Python正则表达式查找最长数字子串(好未来2017笔试题)

    问题描述:读入一个字符串str,输出字符串str中的连续最长的数字串。 思路与代码: def longest1(s): '''查找所有连续数字''' imp...

    Python小屋屋主
  • js中判断字符串是否为合法的email格式

    源哥
  • Q20 Valid Parentheses

    Given a string containing just the characters '(', ')', '{', '}', '[' and ']', d...

    echobingo
  • [数据结构与算法] 邂逅栈

    栈的英文为(stack): 又名堆栈,它是一种运算受限的线性表。限定仅在表尾(栈顶)进行插入和删除操作的线性表

    时间静止不是简史
  • 老瓶装新酒 - C#调用WM手机发送短信(源码)

    一些系统,需要能够发送短信,量很小,平均每日10条。 运营商平台太贵,白名单很严格,小额只能发省内; 各短信平台有各种限制,大事件前后会关闭; 飞信以前可以用W...

    大石头
  • 一天一大 leet(验证回文串)难度:简单 DAY-19

    前端小书童
  • js sort方法根据数组中对象的某一个属性值进行排序

    sort方法接收一个函数作为参数,这里嵌套一层函数用来接收对象属性名,其他部分代码与正常使用sort方法相同.

    TimothyJia
  • 几种分布式锁的实现方式

    基于数据库的分布式锁, 常用的一种方式是使用表的唯一约束特性。当往数据库中成功插入一条数据时, 代表只获取到锁。将这条数据从数据库中删除,则释放送。

    终身幼稚园

扫码关注云+社区

领取腾讯云代金券