Python编程求质数实例代码

本文研究的主要是Python编程求质数实例，选取了几个数进行了测试，具体如下。

定义：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

我们知道自然数(除了0和1以外)都可以写成几个质数相乘再乘以一的格式，所以我们可以用以个数去试一试看看它能否将小于它的质数整除。

首先我们创建一个空的list，然后我们知道2是最小的质数,于是我们把2添加进这个空白的list，之后我们开始循环,第一个数从3开始，用3除以小于3的质数,没有小于它的质数能被它整除，我们将3再添加入我们所创建的list，然后循环到4,在list中有一个质数2能将它整除,我们就舍去这个数因为它不是我们所要的质数。后面的以此类推,合数被舍去,质数保存到list中，最后打印出list就是我们所要的质数合集啦。

import time
start=time.clock()
i=input('please enter an integer:')
#创建一个空list
r=list()
#添加元素2
r.append(2)
#从3开始挨个筛选
for a in range(3,i):
  b=False
#用a除以小于a的质数b
  for b in r:
    if a%b==0:
      b=False
      break
    else:
      b=True
  if b==True:
    r.append(a)
print r
t=(time.clock()-start)
print t

如下显示：

下面用1000来测试代码的结果：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
3.29336980871

这段代码需要用到一点点list的知识,(学校上课刚好讲到这里)，正好可以练习一下如何添加和调用list中的元素哦!

我们来对比一下最容易想到的的办法的效率

import time
start=time.clock()
b=False
i=input('enter an integer please:')
for a in range(2,i):
  for c in range(2,a):
    if a%c==0:
      b=False
      break
    else:
      b=True
  if b==True:
    print a,
elapsed=(time.clock()-start)
print elapsed

运行结果为：

enter an integer please:200
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 2.86033831663
>>>

运行起来明显比前一段代码要迟钝。

下面，使用第一段代码求100000以内的质数，实在是有些卡，下面结果供参考（仅截取了部分结果）：

总结

以上就是本文关于Python编程求质数实例代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

您可能感兴趣的文章:

  • Python 判断是否为质数或素数的实例
  • 使用Python判断质数(素数)的简单方法讲解
  • python实现挑选出来100以内的质数
赞 (0)

相关推荐

  • Python 判断是否为质数或素数的实例

    一个大于1的自然数,除了1和它本身外,不能被其他自然数(质数)整除(2, 3, 5, 7等),换句话说就是该数除了1和它本身以外不再有其他的因数. 首先我们来第一个传统的判断思路: def handlerNum(num): # 质数大于 1 if num > 1: # 查看是否有其他因子 for i in range(2, num//2+1): if (num % i) == 0: print(num,"不是质数") break else: print(num, "是质

  • 使用Python判断质数(素数)的简单方法讲解

    质数又称素数.指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数.素数在数论中有着很重要的地位.比1大但不是素数的数称为合数.1和0既非素数也非合数.质数是与合数相对立的两个概念,二者构成了数论当中最基础的定义之一.基于质数定义的基础之上而建立的问题有很多世界级的难题,如哥德巴赫猜想等.算术基本定理证明每个大于1的正整数都可以写成素数的乘积,并且这种乘积的形式是唯一的.这个定理的重要一点是,将1排斥在素数集合以外.如果1被认为是素数,那么这些严格的阐述就不得不加上一些限制条

  • python实现挑选出来100以内的质数

    这里给大家分享的是使用python实现将100以内的质数挑选出来 代码非常简单,就不多废话了. """ 使用filter将100以内的质数挑选出来 """ # coding = utf-8 import math def func_get_prime(n): return filter(lambda x: not [x%i for i in range(2, int(math.sqrt(x))+1) if x%i ==0], range(2,n+

  • Python编程求质数实例代码

    Python编程求质数实例代码

    本文研究的主要是Python编程求质数实例,选取了几个数进行了测试,具体如下. 定义:质数又称素数.一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数:否则称为合数. 我们知道自然数(除了0和1以外)都可以写成几个质数相乘再乘以一的格式,所以我们可以用以个数去试一试看看它能否将小于它的质数整除. 首先我们创建一个空的list,然后我们知道2是最小的质数,于是我们把2添加进这个空白的list,之后我们开始循环,第一个数从3开始,用3除以小于3的质数,没有小于它的质数能被它整除,

  • python编程嵌套函数实例代码

    python,函数嵌套,到底是个什么东东? 很少有人用,但是,有时确实会用: def multiplier(factor): def multiplyByFactor(number): return number*factor return multiplyByFactor python程序,一个函数在另外一个函数的里面,外层的函数返回的是里层函数.也就是函数本身被返回了,返回的是函数(听起来和C语言的一些东东相似). 注意,返回的函数还可以访问它的定义所在的作用域,也就是它带着它的环境信息奥.

  • python实现Adapter模式实例代码

    python实现Adapter模式实例代码

    本文研究的主要是python实现Adapter模式的相关内容,具体实现代码如下. Adapter模式有两种实现方式一种是类方式. #理解 #就是电源适配器的原理吧,将本来不兼容的接口类能够工作 #这个是类实现方式 #例子 #假如一个插座类输出脚是3脚的,而台灯需要的是两脚插座,现在就需要一个Adapter实现适配插座 #Adaptee class socket(object): def Trigle(self): print 'power supply' #target class tableL

  • python实现Decorator模式实例代码

    本文研究的主要是python实现Decorator模式,具体介绍如下. 一般来说,装饰器是一个函数,接受一个函数(或者类)作为参数,返回值也是也是一个函数(或者类).首先来看一个简单的例子: # -*- coding: utf-8 -*- def log_cost_time(func): def wrapped(*args, **kwargs): import time begin = time.time() try: return func(*args, **kwargs) finally:

  • python编程羊车门问题代码示例

    问题: 有3扇关闭的门,一扇门后面停着汽车,其余门后是山羊,只有主持人知道每扇门后面是什么.参赛者可以选择一扇门,在开启它之前,主持人会开启另外一扇门,露出门后的山羊,然后允许参赛者更换自己的选择. 请问: 1.按照你的第一感觉回答,你觉得不换选择能有更高的几率获得汽车,还是换选择能有更高的几率获得汽车?或几率没有发生变化? 答:第一感觉换与不换获奖几率没有发生变化. 2.请自己认真分析一下"不换选择能有更高的几率获得汽车,还是换选择能有更高的几率获得汽车?或几率没有发生变化?" 写出

  • Python ldap实现登录实例代码

    下面一段代码是小编给大家介绍的Python ldap实现登录实例代码,一起看看吧 ldap_config = { 'ldap_path': 'ldap://xx.xx.xx.xx:389', 'base_dn': 'ou=users,dc=ledo,dc=com', 'ldap_user': 'uid=reporttest,ou=users,dc=ledo,dc=com', 'ldap_pass': '111111.0', 'original_pass': '111111.0' } ldap_m

  • python+matplotlib演示电偶极子实例代码

    python+matplotlib演示电偶极子实例代码

    使用matplotlib.tri.CubicTriInterpolator.演示变化率计算: 完整实例: from matplotlib.tri import ( Triangulation, UniformTriRefiner, CubicTriInterpolator) import matplotlib.pyplot as plt import matplotlib.cm as cm import numpy as np #---------------------------------

  • python的re正则表达式实例代码

    本文研究的主要是python的re正则表达式的相关内容,具体如下. 概念:正则表达式(通项公式)是用来简洁表达一组字符串的表达式.优势是简洁,一行胜千言. 应用:字符串匹配. 实例代码: CODEC = 'UTF-8' #encoding:utf-8 import re p=re.compile("ab") str = "abfffa" #match必须匹配首字母 if p.match(str): print p.match(str).group() #match必

  • python模块之paramiko实例代码

    本文研究的主要是python模块之paramiko的相关用法,具体实现代码如下,一起来看看. paramiko模块提供了ssh及sft进行远程登录服务器执行命令和上传下载文件的功能.这是一个第三方的软件包,使用之前需要安装. 1 基于用户名和密码的 sshclient 方式登录 # 建立一个sshclient对象 ssh = paramiko.SSHClient() # 允许将信任的主机自动加入到host_allow 列表,此方法必须放在connect方法的前面 ssh.set_missing_

  • 简单的python协同过滤程序实例代码

    本文研究的主要是python协同过滤程序的相关内容,具体介绍如下. 关于协同过滤的一个最经典的例子就是看电影,有时候不知道哪一部电影是我们喜欢的或者评分比较高的,那么通常的做法就是问问周围的朋友,看看最近有什么好的电影推荐.在问的时候,都习惯于问跟自己口味差不多的朋友,这就是协同过滤的核心思想. 这个程序完全是为了应付大数据分析与计算的课程作业所写的一个小程序,先上程序,一共55行.不在意细节的话,55行的程序已经表现出了协同过滤的特性了.就是对每一个用户找4个最接近的用户,然后进行推荐,在选择

随机推荐