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

相关文章

解决sublime+python3无法输出中文的问题

Tools -> Build System -> Build New System { "cmd": ["/usr/local/bin/python3", "-u",...

python日期时间转为字符串或者格式化输出的实例

如下所示: 年月日时分秒 >>> print datetime.datetime.now().strftime("%Y-%m-%d %H:%M:%S") 2017-...

Python中循环引用(import)失败的解决方法

前言 最近在开发智能家居项目hestia-rpi项目中,由于代码结构层级划分不合理,导致了循环引用(import)module失败的问题,错误如下: Traceback (most r...

Python 经典算法100及解析(小结)

1:找出字符串s="aaabbbccceeefff111144444"中,字符出现次数最多的字符 (1)考虑去重,首先将字符串进行过滤去重,这样在根据这些字符进行循环查询时,将会减少循...

Python高效编程技巧

下面我挑选出的这几个技巧常常会被人们忽略,但它们在日常编程中能真正的给我们带来不少帮助。 1. 字典推导(Dictionary comprehensions)和集合推导(Set comp...