关于生成质数 (Prime Number) 的思路


最近在学习MIT的在线计算机科学入门课程,碰到了生成质数的问题。

所谓的质数,就是在大于1的正整数中,因数只有1和其本身的整数。比如2,3,5……。

第一反应之下,我只想到最笨的办法:

def genPrimesDirectly():
  '''Generate Prime Numbers using Python generator.
    It is the worst economic method I can think of. The complexity should be O(nlog(n))
    Written by aresowj on 08/09/2015'''
  n = 2		#First number
  yield n
    
  while True:
    n += 1						#Start from 3
    for i in range(2, n):		#Calculates every number from 2 to n-1 to confirm if any factor of n
      if n % i == 0:
        break
      elif i == n - 1:		#If i is the last number in the sequence and i is not a factor of n, n is a prime number. Then yield it.
        yield n

能够改进的地方还是有的,那就是缩小在判断每一个数字时用来求余的范围。在笨办法里,程序将用 [2, n-1] 这个区间里的每个数对n求余,如果发现n能够被区间内的某个数除尽,则判断n不是质数,从而跳到下一个n的判断中。

然而,实际上我们只需要在[2, sqrt(n)]这个范围内进行判断就好了。其原因在于,因数都是成对出现的,比如100的因数有1和100,2和50,4和25……10和10。可以看出,成对的因数会逐渐地互相“靠近”,并且总有一个因数小于等于该数的平方根,另一个因数大于等于该数的平方根。

import math

def genPrimesModified():
  '''Generate Prime Numbers using Python generator.
    Instead of looping from 2 to n, the better way is to set the end point at sqrt(n). The complexity should be O(n(log(logn)))
    Written by aresowj on 08/09/2015'''
  n = 2		#First number
  yield n
  n = 3		#Second number
  yield n
    
  while True:
    n += 1				#We would like to start from number 4 because number 3 will not trigger the for loop and will be ingnored.
    for i in range(2, int(math.sqrt(n))+1):
      if n % i == 0:
        break		#Stop this for loop and turn back to the outer while loop when a number was found to be a factor of n.
      elif i == int(math.sqrt(n)):
        yield n		#If i is the last number in the sequence and i is not a factor of n, n is a prime number. Then yield it.

如果要再进一步优化,就将用于判断的数限定在已经求出的质数里,结束点同样是sqrt(n)。下列代码引用自MIT的在线慕课MITx: 6.00.1x Introduction to Computer Science and Programming Using Python。

'''
Referred from MITx: 6.00.1x Introduction to Computer Science and Programming Using Python, Lecture 12
URL: https://courses.edx.org/courses/course-v1:MITx+6.00.1x_6+2T2015/courseware/Week_6/videosequence:Lecture_11/
'''

# Note that our solution makes use of the for/else clause, which 
# you can read more about here:
# http://docs.python.org/release/1.5/tut/node23.html 

def genPrimes():
    primes = []   # primes generated so far
    last = 1      # last number tried
    while True:
        last += 1
        for p in primes:
            if last % p == 0:
                break
        else:
            primes.append(last)
            yield last

我又想起来,之前好像在哪看过一个“筛选法”,是用排除的办法来选出质数。思路如下:

  1. 确定要求质数的范围,比如[2, 100];
  2. 从最小的质数2开始,将范围中2的倍数全部剔除,然后将下一个整数的倍数也都剔除;
  3. 如此循环下去,剩下的就全是质数了。

可以用一张动画来形象地表示这个过程:

Find prime numbers

 

然而,这个办法主要针对于已经确定了求值范围的情况。如果要写出一个更有效的可以不断生成新质数的函数,就应该在上述代码的基础上改进一下。各位可以参考一下廖雪峰老师在其Python 3教程使用filter函数实现的办法:filter – 廖雪峰的官方网站

 

 

One thought on “关于生成质数 (Prime Number) 的思路”

  1. 这个问题其实已经被研究到烂啦,至少当初我在初中的时候就有在筛法的基础上只看尾数的优化,例如只看一个尾数的时候,只有尾数是1,3,7,9的才有可能是质数。效率提高不少

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s