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

相关文章

跟老齐学Python之传说中的函数编写条规

关于函数的事情,总是说不完的,下面就罗列一些编写函数的注意事项。特别声明,这些事项不是我总结的,我是从一本名字为《Learning Python》的书里面抄过来的,顺便写成了汉语,当然,...

在Python中编写数据库模块的教程

在一个Web App中,所有数据,包括用户信息、发布的日志、评论等,都存储在数据库中。在awesome-python-app中,我们选择MySQL作为数据库。 Web App里面有很多地...

基于python list对象中嵌套元组使用sort时的排序方法

在list中嵌套元组,在进行sort排序的时候,产生的是原数组的副本,排序过程中,先根据第一个字段进行从小到大排序,如果第一个字段相同的话,再根据第二个字段进行排序,依次类推,当涉及到字...

python相似模块用例

一:threading VS Thread 众所周知,python是支持多线程的,而且是native的线程,其中threading是对Thread模块做了包装,可以更加方面的被使用,th...

Python实现二叉树的常见遍历操作总结【7种方法】

本文实例讲述了Python实现二叉树的常见遍历操作。分享给大家供大家参考,具体如下: 二叉树的定义: class TreeNode: def __init__(self, x):...