关于生成质数 (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的判断中。 继续阅读关于生成质数 (Prime Number) 的思路

Python自学笔记02 – 字符串

上一篇:Python自学笔记01 – 基本语法

下一篇:Python自学笔记03 – 控制流程


 

字符串(Strings)

和变量相同,要获得一个字符串,只要直接向一个名称赋予字符便可,不需要独立声明。如:

 my_string = "Hello Python!" 

继续阅读Python自学笔记02 – 字符串

Python自学笔记01 – 基本语法

使用http://www.codecademy.com/进行在线学习。

推荐这个编程学习网站,对初学者非常友善。

笔记用于记录关键点,会插入一点自己的想法。


 

Print语句

类似于PHP中的Print,直接在该关键字后接需要输出的内容即可。

 

变量(Variable)

Python中的变量不需要经过定义即可使用,并且系统会在你赋值时自动判断其类型。

这一点与C/C++完全不同。

继续阅读Python自学笔记01 – 基本语法