为了学习Python,最好还是直接从写代码入手,解决的问题如下:
1、使用质数的定义求出所有小于等于1000000的质数
2、使用筛法求出所有小于等于1000000的质数,并比较两种方法的耗时。数据说话
3、从小到大,求出前m个素数。这里先使用素数定理x/lin(x)=m,预估出前m个素数分布的范围
再使用筛选法求出
#coding=utf-8 ''' Created on 2015年8月14日 @author: zwustudy 1、输出所有小于等于max的质数,这里提供两种方法: producePrime1使用质数判断方法,一直遍历到某一个数的平方根值 producePrime2使用筛法,筛选剔除小于等于max的所有非质数,剩下的就是质数了 2、从小到大,输出前m个质数。 筛法的速度远超普通方法,针对这个需求,普通方法很慢,筛法又不适用,因为不知道前m个质数对应的max是多少, 这怎么办呢?质数越往后越稀疏,有个素数定理就是用来预估max以内有多少质数,最简洁的公式有x/ln(x),会有一定的误差,但是不超过百分之十五 那么我们可以根据m反推出max的大小 ''' import math import time ''' 最朴素的判断质数的方法, 即根据质数的定义,一直从2到该数的平方根,判断是否能整除 ''' def producePrime1(max): for i in range(2, max + 1): if __isPrime(i): print i ''' 筛选法找质数,即“埃拉托色尼筛法”,挖掉2的倍数、3的倍数、一直到max的平方根的倍数,剩下的都是质数了 ''' def producePrime2(max): li = [] for i in range(2, max + 1): if i > 2 and i % 2 == 0: li.append(0) else: li.append(i) for i in range(3, int(math.sqrt(max)) + 1, 2): if li[i - 2] != 0: for j in range(i + i, max + 1, i): li[j - 2] = 0 for i in li: if i != 0: print i ''' 从小到大,输出前count(count > 10)个质数 这里先使用素数定理求出count个素数分布的范围,再使用筛选法筛除所有素数,最后输出前count个素数 ''' def producePrePrime(count): max = int(__findMax(count) * 1.15) li = [] for i in range(2, max + 1): if i > 2 and i % 2 == 0: li.append(0) else: li.append(i) for i in range(3, int(math.sqrt(max)) + 1, 2): if li[i - 2] != 0: for j in range(i + i, max + 1, i): li[j - 2] = 0 j = 0 for i in li: if i != 0: print i j += 1 if j >= count: break ''' 判断number是否是质数 ''' def __isPrime(number): if number <= 1 : return False for i in range(2, int(math.sqrt(number)) + 1): if number % i == 0 : return False return True ''' 根据素数定理,x/ln(x) >= m 找到最小的一个整数x解,m > 10 ''' def __findMax(m): if m <= 10: raise NameError('input illeagal m <= 10!') start = m end = m * 2 while True: if end / math.log(end,math.e) >= m: break; start = end end = end * 2 index = int((start + end) / 2) while True: m1 = index / math.log(index, math.e) m2 = (index - 1) / math.log(index - 1, math.e) if m1 >= m and m2 < m: break; if m1 >= m: end = index else: start = index index = int((start + end) / 2) return index max = 1000000 start = long(time.time() * 1000) producePrime1(max) end1 = long(time.time() * 1000) producePrime2(max) end2 = long(time.time() * 1000) producePrePrime(10000) print("使用质数定义法找出所有小于等于" + str(max) + "质数并输出,总共耗时" + str(end1 - start) + "毫秒") print("使用筛选法找出所有小于等于" + str(max) + "质数并输出,总共耗时" + str(end2 - end1) + "毫秒")
运行结果如下图:
代码我也放到GitHub上面了
相关推荐
Python的学习记录与分享——PTA程序设计类教学平台。如果你也正在学习关于此类的题目可以仔细阅读这篇文章,了解一下循环结构、素数的基本语法知识。 题目: 7-5就区间正整数内所有素数之和 (20分) 【描述】求m-n...
主要介绍了Python 2种方法求某个范围内的所有素数(质数),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
任务53: 尚硅谷_Python基础_53_质数练习第一次优化18:16 任务54: 尚硅谷_Python基础_54_质数练习第二次优化11:10 任务55: 尚硅谷_Python基础_55_《唐僧大战白骨精》分析12:43 任务56: 尚硅谷_Python基础_56_...
在本篇文章里小编给大家分享的是关于python如何求100以内的素数的方法实例,需要的朋友们可以学习下。
Python学习 作业:创建一个 Tic Tac Toe 游戏要求: 2 名玩家应该能够玩游戏(两人坐在同一台电脑上) 每次玩家移动时都应该打印出棋盘 您应该能够接受玩家的输入定位,然后在板上放置一个符号 Fibonacci series ...
Python学习,代码文档_素数判定
本文研究的主要是Python编程求质数实例,选取了几个数进行了测试,具体如下。 定义:质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。 我们知道自然数(除了0和...
python语言对于计算机专业的学生,不管是计算机软件还是物联网,都是很重要的一种编程语言,python未来在人工智能方向上是会有很大的贡献程度...python学习—–使用列表实现筛选法求素数目录一、列表实现筛选法求素数的
Python3 100例 实例001:数字组合 实例002:“个税计算” 实例003:完全平方数 实例004:这天第几天 实例005:三数排序 实例006:斐波那契数列 实例007:copy 实例008:九九乘法表 实例...
作为学习Python的示例,下面是一个高效求解一个范围内的素数的程序,不需要使用除法或者求模运算。 #coding:utf-8 #设置python文件的编码为utf-8,这样就可以写入中文注释 def primeRange(n): myArray=[1 for x in...
python程序设计实践教程张莉答案_Python程序设计(2018年 春) 本课程主要⾯向⾮计算机专业学习者,不局限某个专业和学历层次,需要⼀些程序设计的基本概念如计算机求解问题的框架和⼀些如素数判 断这样的基本算法,...
Java经典问题100例,相信很多编程者都知道,被很多语言重写,今天的源码包是用Python语言重写的Java经典100例源码,同样是学习python编程的经典范例,学习python的一定要看哦。 ps:除JCP077.py外,所有代码文件都...
python判断素数
Miller_Rabin素数判断法,大整数快速因式分解算法(pollard_rho算法),生成指定位数的大质数或大整数算法等。 3、RSA算法库。使用上面两个库,实现RSA算法。实现了生成指定数位的密钥对,加密,解密,签名和验证,...
python教程利用python3代码实现输出第n个素数源码分享,下载即可运行,欢迎下载学习
本课程主要面向非计算机专业学习者,不局限某个专业和学历层次,需要一些程序设计的基本概念如计算机求解问题的框架和一些如素数判断这样的基本算法,缺少上述基础的同学不用担心,在上课过程中可以根据课程自己进度...
在本篇文章里小编给大家整理了关于python判断素数的方法和代码,需要的朋友们可以学习下。
实验目的:通过对函数及函数式编程的学习,在给定条件或要求下,能够使用自定义函数、递归函数等函数的定义及调用方法,编写...(一)程序一:求正整数n之内(包括n)的所有素数之和 (二)程序二:十进制转换为二进制
用 Python 编写的所有模拟和算法的库。包括从太阳系和重力模拟到排序算法可视化器的程序。所有算法和模拟都是由 Fraser Love -me@fraser.love在 Python 中实现的 模拟和生成器 二维重力模拟 太阳系模拟 Perlin 噪声...
学习Python3 数字 找到第 N 位的 PI - 输入一个数字并让程序生成 PI 到小数点后的位数。 限制程序的运行范围。 斐波那契数列 - 输入一个数字,让程序生成该数字或第 N 个数字的斐波那契数列。 Prime ...