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

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

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.

'''
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
# 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. 如此循环下去，剩下的就全是质数了。

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

1. 匿名说道：

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