Python实现高效求解素数代码实例

yipeiwu_com5年前Python基础

素数是编程中经常需要用到的。

作为学习Python的示例,下面是一个高效求解一个范围内的素数的程序,不需要使用除法或者求模运算。

#coding:utf-8    #设置python文件的编码为utf-8,这样就可以写入中文注释
def primeRange(n):
  myArray=[1 for x in range(n+1)] ##列表解析,生成长度为(n+1)的列表,每个数值都为1
  myArray[0]=0
  myArray[1]=0
  startPos=2
  while startPos <= n:
    if myArray[startPos]==1:
      key=2
      resultPos = startPos * key #可知startPos的整数倍都不是素数,设置startPos的整数倍的位置为0表示非素数
      while resultPos <= n:
        myArray[resultPos] =0
        key += 1
        resultPos = startPos *key
    startPos += 1

  resultList=[]  ##将最终的素数保存在resultList列表返回
  startPos=0
  while startPos <= n:
    if myArray[startPos] == 1:
      resultList.append(startPos)
    startPos += 1
  return resultList

numString=raw_input("Input the Range(>3):")
numInt=int(numString)
if numInt <= 3:
  print "The Number Need to be greater than 3"
else:
  primeResult=primeRange(numInt)
  print "The Result is:",primeResult

相关文章

django admin后台添加导出excel功能示例代码

django admin后台添加导出excel功能示例代码

Django功能强大不单在于他先进的编程理念,很多现有的功能模块更是可以直接拿来使用,比如这个牛掰的admin模块,可以作为一个很好的信息登记管理系统。 admin模块中的actioin...

python字典操作实例详解

本文实例为大家分享了python字典操作实例的具体代码,供大家参考,具体内容如下 #!/usr/bin/env python3 # -*- coding: utf-8 -*- im...

pycharm中使用anaconda部署python环境的方法步骤

pycharm中使用anaconda部署python环境的方法步骤

今天来说一下python中一个管理包很好用的工具anaconda,可以轻松实现python中各种包的管理。相信大家都会有这种体验,在pycharm也是有包自动搜索和下载的功能,这个我在前...

PYTHON基础-时间日期处理小结

步骤: 1. 掌握几种对象及其关系 2. 了解每类对象的基本操作方法 3. 通过转化关系转化 涉及对象 1. datetime >>> import datetim...

解决python3中解压zip文件是文件名乱码的问题

在zip标准中,对文件名的 encoding 用的不是 unicode,而可能是各种软件根据系统的默认字符集来采用(此为猜测),因此zipfile中根据文件 flag 检测的时候,只支持...