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中MethodType方法介绍与使用示例

前言 本文主要给大家介绍了关于python中MethodType方法的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍吧 示例代码 #!/usr/bin/python...

Python中获取对象信息的方法

当我们拿到一个对象的引用时,如何知道这个对象是什么类型、有哪些方法呢? 使用type() 首先,我们来判断对象类型,使用type()函数: 基本类型都可以用type()判断: >...

python sorted方法和列表使用解析

python sorted方法和列表使用解析

这篇文章主要介绍了python sorted方法和列表使用解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一、基本形式列表有自己的...

python 计算数组中每个数字出现多少次--“Bucket”桶的思想

python 计算数组中每个数字出现多少次--“Bucket”桶的思想

题目: 解法一:比较元素是否相等 思路说明: 这种应该是普通人最先想到的解法,先获取到数组之后进行有小到大排序,然后初始化一个min=0(代表新数字的开始角标),然后遍历新数组的每一个...

python带参数打包exe及调用方式

1.举个栗子:XX.py import sys arg1 = sys.argv[1] arg2 = sys.argv[2] print(arg1) print(arg2) 平时...