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以内的质数
时间: 2018-01-28

使用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 判断是否为质数或素数的实例

一个大于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判断文件和字符串编码类型的实例

python判断文件和字符串编码类型可以用chardet工具包,可以识别大多数的编码类型.但是前几天在读取一个Windows记事本保存的txt文件时,GBK却被识别成了KOI8-R,无解. 然后就自己写了个简单的编码识别方法,代码如下: coding.py # 说明:UTF兼容ISO8859-1和ASCII,GB18030兼容GBK,GBK兼容GB2312,GB2312兼容ASCII CODES = ['UTF-8', 'UTF-16', 'GB18030', 'BIG5'] # UTF-8 B

python 判断文件还是文件夹的简单实例

如下所示: import os if os.path.isdir(path): print "it's a directory" elif os.path.isfile(path): print "it's a normal file" else: print "it's a special file(socket,FIFO,device file)" 以上这篇python 判断文件还是文件夹的简单实例就是小编分享给大家的全部内容了,希望能给大家

Python 判断文件或目录是否存在的实例代码

使用 os 模块 判断文件是否存在 os.path.isfile(path) 判断目录是否存在 os.path.isdir(path) 判断路径是否存在 # 使用 path 模块 os.path.exists(path) # 使用 access() 方法 os.access(path, os.F_OK) 使用 open 函数和异常捕获 如果直接用 open() 函数打开一个不存在的文件时,程序会抛出异常,我们可以通过 try 语句来捕获异常以达到判断文件是否存在的目的. 如果文件不存在,open

python判断计算机是否有网络连接的实例

先安装第三方库:pip install requests def isConnected(): import requests try: html = requests.get("http://www.baidu.com",timeout=2) except: return False return True 以上这篇python判断计算机是否有网络连接的实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

python 判断三个数字中的最大值实例代码

python 判断三个数字中的最大值,具体代码如下所示: #判断三个数中最大值 n1= int(input('please enter the firest number:')) n2 = int(input('please enter the second number:')) n3 = int(input('please enter the third number:')) max_num = 0 if n1 > n2: max_num = n1 if n1 > n3: max_num =

Python判断变量是否是None写法代码实例

代码中经常会有变量是否为None的判断,有三种主要的写法: 第一种是`if x is None`: 第二种是 `if not x:`: 第三种是`if not x is None`(这句这样理解更清晰`if not (x is None)`) . 如果你觉得这样写没啥区别,那么你可就要小心了,这里面有一个坑.先来看一下代码: >>> x = 1 >>> not x False >>> x = [1] >>> not x False &

python判断所输入的任意一个正整数是否为素数的两种方法

素数(也称质数),是指除了1和该数本身,不能被任何正整数整除的正整数.判断一个正整数m是否为素数,只要判断m可否被2~根号m之中的任何一个正整数整除,如果m不能被此范围中任何一个正整数整除,m即为素数,否则m为合数. 方法一:(利用for循环和break语句) import math m = int(input("请输入一个整数(>1):")) k = int(math.sqrt(m)) for i in range(2, k+2): if m % i == 0: break #

Python编程判断一个正整数是否为素数的方法

本文实例讲述了Python编程判断一个正整数是否为素数的方法.分享给大家供大家参考,具体如下: import string import math #判断是否素数的函数 def isPrime(n): if(n<2): return False; elif(n==2): return True; elif(n>2): for d in range(2,int(math.ceil(math.sqrt(n))+1)): if(n%d==0): return False; return True;