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

相关文章

pytorch AvgPool2d函数使用详解

我就废话不多说了,直接上代码吧! import torch import torch.nn as nn import torch.nn.functional as F from to...

python聚类算法解决方案(rest接口/mpp数据库/json数据/下载图片及数据)

python聚类算法解决方案(rest接口/mpp数据库/json数据/下载图片及数据)

1. 场景描述 一直做java,因项目原因,需要封装一些经典的算法到平台上去,就一边学习python,一边网上寻找经典算法代码,今天介绍下经典的K-means聚类算法,算法原理就不介绍...

Python线程的两种编程方式

Python中如果要使用线程的话,python的lib中提供了两种方式。一种是函数式,一种是用类来包装的线程对象。举两个简单的例子希望起到抛砖引玉的作用,关于多线程编程的其他知识例如互斥...

python正则表达式re模块详细介绍

本模块提供了和Perl里的正则表达式类似的功能,不关是正则表达式本身还是被搜索的字符串,都可以是Unicode字符,这点不用担心,python会处理地和Ascii字符一样漂亮。 正则表...

python数据结构之二叉树的建立实例

先建立二叉树节点,有一个data数据域,left,right 两个指针域复制代码 代码如下:# -*- coding: utf - 8 - *-   &nb...