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

相关文章

浅谈dataframe中更改列属性的方法

在读取文件时将整数变量读成了字符串, 或者需要转换列属性时,通过方法astype Python中 举例: dataframe.numbers=dataframe.numbers.as...

在Python中处理字符串之ljust()方法的使用简介

 ljust()方法返回字符串左对齐的字符串长度宽度。填充是通过使用指定的fillchar(默认为空格)。如果宽度小于len(s)返回原始字符串。 语法 以下是ljust()方...

pandas系列之DataFrame 行列数据筛选实例

pandas系列之DataFrame 行列数据筛选实例

一、对DataFrame的认知 DataFrame的本质是行(index)列(column)索引+多列数据。 为了简化理解,我们不妨换个思路… 现实中,为了简化对一件事物的描述,我们会...

Python中的正则表达式与JSON数据交换格式

Python中的正则表达式与JSON数据交换格式

一、初识正则表达式 正则表达式 是一个特殊的字符序列,一个字符串是否与我们所设定的这样的字符序列,相匹配快速检索文本、实现替换文本的操作 json(xml) 轻量级 web 数据交换格式...

解决python 3 urllib 没有 urlencode 属性的问题

今天在pycharm(我用的python3)练习的时候,发现报了个AttributeError: module 'urllib' has no attribute 'urlencode'...