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

yipeiwu_com6年前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中zfill()方法的使用教程

 zfill()方法用零垫串来填充左边宽度。 语法 以下是zfill()方法的语法: str.zfill(width) 参数    ...

python正则匹配查询港澳通行证办理进度示例分享

复制代码 代码如下:import socketimport re '''广东省公安厅出入境政务服务网护照,通行证办理进度查询。分析网址格式为 http://www.gdcrj.com/w...

python 模拟创建seafile 目录操作示例

本文实例讲述了python 模拟创建seafile 目录操作。分享给大家供大家参考,具体如下: # !/usr/bin/env python # -*- coding: utf-8...

从Python的源码浅要剖析Python的内存管理

从Python的源码浅要剖析Python的内存管理

Python 的内存管理架构(Objects/obmalloc.c): 复制代码 代码如下:     _____   ______&nb...

Python数组条件过滤filter函数使用示例

使用filter函数,实现一个条件判断函数即可。 比如想过滤掉字符串数组中某个敏感词,示范代码如下: #filter out some unwanted tags def pass...