求300以内的素数for循环_更多数学趣题——求质数

求质数

质素也叫素数，只能被自己和1整除，它们是数的骨架，由他们组合可以生成别的数。
它们是人类最着迷的数字，自古就吸引了无数学者学生。

古代的人们就知道素数有无穷多个，这一点被欧几里得所证明。而伟大的数学家欧拉靠心算算出了232-1是一个素数。

我们现在就编程序判断一个数是不是素数。

基本的思路就是

1. 从2开始
2. 一个一个算能否被n整除
3. 如果可以被整除，就说明不是素数

如果我们动一下脑筋，就会看出不需要算到n，因为很明显因子不会大于n/2。我们再深入思考一下，会发现也不需要判断到n/2，只需要判断到n的平方根就可以了。

import math
def isprime(n):
    for x in range(2, int(math.sqrt(n))+1):
        if n % x == 0:
            return 0
    return 1

上面的程序引用了Python自带的math库。

用到了math.sqrt()函数。

程序的主体就是这个for循环，从2开始一个个检查到n的平方根，只要能被整除就将标志设为1。

注意range的上下限，是左闭右开的，所以要给平方根+1。

有了这个判断的方法，列出小于n之内的所有素数就比较简单了，示例如下：

def primes(x):
for i in range(2,x+1):
  if isprime(i):
  print(i)
primes(100)

上面的程序把小于给定的数x的所有素数打印输出来。

这么些虽然没有什么错，但是我们一般不建议在函数中打印输出，这样别的程序就没有办法重用这个函数了。

我们可以改造一下，用一个数组记录下所有素数，返回给客户程序使用：

def primes(x):
    pa = []
    for i in range(2,x):
        if isprime(i):
            pa.append(i)
    return pa
print(primes(100))

而有的时候，我们并不想存这么多数据（如果上面这个函式给的参数值很大，返回的数组也会很大），只是想一个一个拿到这些数据，有没有办法呢？

有的，用迭代就可以了，它既可以返回数据又不需要事先存放那么多数据，而是在循环迭代的过程中拿到数据的。

我们看程序：

def primes(x):
    for i in range(2,x):
        if isprime(i):
            yield i

这个函数里有一个特别的命令yield，这个命令你可以理解为return，把一个素数返回了。

但是这种写法下，Python进行了特殊处理，给你生成了一个迭代器，你可以用迭代器一个一个拿数据。我们看主程序怎么写的：

r = primes(100)
while True:
    try:
        print(next(r))
    except StopIteration:
        Break

程序第一条语句

r = primes(100)

定义了一个迭代器，然后程序进入无限循环，输出next(r)，这个函数执行下一个迭代。

直到迭代停止。

看具体的过程，第一次执行next(r)的时候，跟普通函数一样，执行的是primes函数的这条语句for i in range(2,x)，x为100，i=2，符合条件，所以执行循环体里的第一条语句if isprime(i)，判断为真，所以执行yield i，相当于返回了2。

然后回到了主程序。

主程序先输出返回的2，然后开始下一个循环，所以又一次执行next(r)， 注意了，不是重新调用primes函数，而是执行r的第二次迭代，也就是说接着上一次的迭代返回点继续执行，所以还是执行的是primes函数的这条语句for i in range(2,x)，x为100，i=3，符合条件，所以执行循环体里的第一条语句if isprime(i)，判断为真，所以执行yield i，相当于返回了3。然后回到了主程序。

主程序先输出返回的3，然后开始下一个循环，所以还是执行next(r)，执行r的第三次迭代，也就是说接着上一次的迭代返回点继续执行，所以还是执行的是primes函数的这条语句for i in range(2,x)，x为100，i=4，符合条件，所以执行循环体里的第一条语句if isprime(i)，判断为假，所以循环回来执行语句for i in range(2,x)，x为100，i=5，符合条件，执行循环体里的第一条语句if isprime(i)，判断为真，执行yield i，相当于返回了5。然后回到了主程序。

这样一直迭代，到最后i超过100了，就迭代出错，停止，这就是语句except StopIteration的作用。

还有一种写法，可以让Python自动判断，不需要手工处理迭代异常：

for i in primes(100):
    print(i)

这个for语句在Python的解释下，执行的其实是迭代next。

当然，你肯定会觉得yield很古怪，我理解你的这种感受。我们其实还有一种不用yield的办法实现同样的功能。那就是自己创造一个迭代器，程序如下：

class primes(object):
    def __init__(self, n):
        self.n=n
        self.i=1
    def __iter__(self):
        return self
    def __next__(self):
        while self.i<self.n:
            self.i += 1
            if isprime(self.i):
                return self.i
        raise StopIteration()

这段程序有几个你不熟悉的地方，第一个关键字class，这是表示定义一个类，而不是函数，类可以看成一个包，包含了函数和变量，后面对函数和变量的引用都要加上对象的名字。

类名后面的object是父类的名字，表示我们定义的primes类是继承于object的子类。我们看我们定义的这个类里面有三个函数

__init__(), __iter__(), __next()_

函数名字也比较奇怪，前后加了__。这表示是Python系统规定的名字。顾名思义，init是类初始化的函数，iter是一个协议规定，必须有这么一个函数才能叫迭代器，next表示迭代程序执行体。

调用程序还是没有变化：

r = primes(100)
while True:
    try:
        print(r.next())
    except StopIteration:
        break

或者仍然使用Python的for循环：

r=primes(100)
for i in r:
    print(i)

对于这个主程序，r=primes(100)手工创建了一个可迭代的对象。100作为参数自动传给__init__函数，对象就记录下self.n这个值为100了，循环数self.i初始化为1。

for循环进行迭代，每次都会执行__next__()，只要self.i<self.n就把循环数self.i加1，然后判断是不是素数，如果是就返回。主程序的for循环进行第二次迭代的时候，还是执行对象的__next__()，这个时候对象没变，记录的是上一次的值。这就相当于yield了。从代码的简短来讲，yield更有优势，从程序结构来讲，iterator更加好。

到此，我们就接触到了Python的面向对象编程。

在中国大名鼎鼎的哥德巴赫猜想，也是关于素数的，一个大偶数（>=6）可以表示为两个素数之后。这个猜想一直是一个猜想，没有得到完全证明，中国数学家陈景润得到了最好的结果1+2。陈景润的故事堪称几代中国人口中的传奇，全国妇孺皆知，在那个刚刚开始解冻的岁月里，陈景润成了“科学的春天”最好的注脚。不过我们也要客观地了解到，哥德巴赫猜想在数学上的地位并不是我们普通人想象的那么高。

我们自己没有那个本事证明哥德巴赫猜想，但是我们可以编一个程序来验证哥德巴赫猜想。这个我们可以利用计算机的快，通过暴力枚举求解。程序如下：

x=100
#list all prime numbers less than x
pa = []
for i in range(2,x):
    if isPrime(i):
        pa.append(i)
print(pa)
 
#add each number pair
j=0
while j<len(pa) :
    k = j
    while k<len(pa):
        if pa[j]+pa[k]==x:
            print(x,pa[j],pa[k])
        k += 1
    j += 1

程序先把小于给定的数x的所有素数求出来，放到一个pa数组中。pa.append(i)语句的作用是往pa数组中添加一个新元素i。得出这个数组后，就两两组合，看这些数是不是相加等于x。核心就是两重循环，第一个循环定下第一个值：是从数组中逐个拿每一个值pa[j]，第二个循环就是定下第二个值：拿到第一个值之后的每一个值，然后相加检查。

对100，程序运行结果是：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

100 3  97
100 11 89
100 17 83
100 29 71
100 41 59
100 47 53

成对的素数也有无穷多个，有一个有名的数学猜想是“孪生素数猜想”，即相差为2的素数对有无穷多个。2013年，张益唐博士证明了有界素数对问题，突破百年僵局，接近解决这个猜想。张益唐一生坎坷，在美国曾经打零工洗盘子记账送外卖谋生，一直没有固定工作，但他一直锲而不舍地钻研数学大问题，最后终于在58岁的时候取得了历史性成就，有纪录片专门介绍他（《Counting From Infinity》，中文我翻译成“数无涯者”）。他自评“庾信平生最萧瑟，暮年诗赋动江关。”，我觉得这就是历史定评。

我们写一段程序列出孪生素数：

x=100
#list all prime numbers less than x
pa = []
for i in range(2,x):
    if isPrime(i):
        pa.append(i)
print(pa)
 
#twins
j=0
k=j+1
while j<len(pa)-1 :
    if pa[k]-pa[j]==2:
        print(pa[j],pa[k])
    j += 1
    k = j+1

从上面的这些例子可以看出，证明一个定理和验证一个定理是完全不同的事情。验证一个结论可能很简单，但是严格证明却是非常困难的。同时我们也看到了，验证再多的数都不能证明猜想，因为数是无穷多的。所以实践并不是检验真理的标准，逻辑证明才是。

素数的分布问题从古到今就被世人所热衷，一直是数论中最重要最中心的问题。

从素数表可以看出：在1到100中间有25个素数,在1到1000中间有168个素数,在1000到2000中间有135个素数, 在2000到3000中间有127个素数，在3000到4000中间有120个素数,在4000到5000中间有119个素数,在5000到10000中间有560个素数。由此可看出，素数的分布越往上越稀少。

通过计算和初步研究发现，素数分布是以黎曼公式为中心，高斯公式为上限的正态分布。但是始终没有被证明。黎曼发现了质数分布的奥秘完全蕴藏在一个特殊的函数之中，尤其是使那个函数取值为零的一系列特殊的点对质数分布的细致规律有着决定性的影响。所以一直只能叫黎曼猜想。希尔伯特23个问题就有黎曼猜想，克雷研究所千禧问题也有黎曼猜想，可以说黎曼猜想是一座巍峨的高峰，吸引无数天才人物攀登。

质数的定义简单得可以在小学课上进行讲授，但它们的分布却奥妙得异乎寻常，数学家们付出了极大的心力，却迄今仍未能彻底了解。

真理总是简单，而认识真理很难。