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