如何求解素数？

给定一个正整数N，如何求解小于等于N的所有素数？

如：

输入：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

如何分析这个算法呢？如果要求不大于N的所有的素数，很明显思路应该是从1到N逐一检测是不是素数。

所以，伪代码可以写为：

N = int(input())

n = 2

while n <= N:

      if n is a prime number:

            print(n)

      n = n + 1

现在问题归结为判断一个数n是不是素数的问题，这样将一个大问题化解为小问题来进行求解，这是解决算法问题的一大思路。那么问题来了，该如何判定一个数是否是素数呢？

我们需要通过以下四步来完成：

1、先获取n的所有的可能的因子，即2,3,4，...，n-1；

2、检查n是否含有上述可能的因子；

3、若n含有上述因子，则n是合数；

4、若n不含有上述因子，则n是素数。

根据伪代码可以写出版本1代码：

n = int(input("Please type a positive integer, greater than 1: "))

factor = 2
isPrime = True

while factor < n:
    if (n % factor == 0):
        isPrime = False

    factor = factor + 1

if isPrime:
    print(n, " is a prime.")
else:
    print(n, " is a composite.")

这里，应用布尔变量isPrime表示一个数是否是素数。但是有什么优化的空间呢？

根据定义，我们知道，只要n具有2到n-1之间的一个因子，那么n肯定不是素数，也就是说，一旦发现n具有其中的一个因子，后续的循环是没必要的。怎么终止循环呢？程序中一般使用break关键字来结束循环。注意与continue关键字的区别，continue是结束本次循环而进行下一次循环，而break是终止for或者while循环。稍作修改，得到版本2的代码：

n = int(input("Please type a positive integer, greater than 1: "))

factor = 2
isPrime = True

while factor < n:
    if (n % factor == 0):
        isPrime = False
        break
    factor = factor + 1

if isPrime:
    print(n, " is a prime.")
else:
    print(n, " is a composite.")

但是还有什么优化的空间呢？我们知道，sqrt(n)*sqrt(n) = n，所以一旦n具有大于sqrt(n)的因子，必然有相对应的小于sqrt(n)的因子。那么，我们只需要检测2到sqrt(n)之间的所有因子。修改可得版本3的代码：

import math

n = int(input("Please type a positive integer, greater than 1: "))

factor = 2  # initial value of possible factor
isPrime = True  # variable to remember if n is a prime or not
factorUpperBound = math.sqrt(n)  # the largest possible factor we need to test is sqrt(n)

# loop to generate and test all possible factors
while (factor <= factorUpperBound):
    # test if n is evenly divisible by factor
    if (n % factor == 0):
        isPrime = False
        break

    factor = factor + 1

# Output
if isPrime:
    print(n, " is a prime.")
else:
    print(n, " is a composite.")

代码还有一种实现方式，就是不在使用break而使用布尔类型的变量进行and来操作，得到版本4的代码：

# Programmer: Python那些事
# Date: April 14, 2017
# This program reads a positive integer, greater than 1 and
# determines whether this integer is a prime or not.

import math

n = int(input("Please type a positive integer, greater than 1: "))

factor = 2  # initial value of possible factor
isPrime = True  # variable to remember if n is a prime or not
factorUpperBound = math.sqrt(n)  # the largest possible factor we need to test is sqrt(n)

# loop to generate and test all possible factors
while (factor <= factorUpperBound) and (isPrime):
    # test if n is evenly divisible by factor
    if (n % factor == 0):
        isPrime = False

    factor = factor + 1

# Output
if isPrime:
    print(n, " is a prime.")
else:
    print(n, " is a composite.")

现在，有了以上判定一个数是否素数的代码，可以回到主问题了，得到最终版本的代码了：

# Programmer: Python那些事
# Date: April 14, 2017
# This program reads a positive integer, greater than 1 and
# prints all the primes smaller than the integer.

import math

N = int(input("Please type a positive integer, greater than 1: "))

n = 2  # n will take on values from 2 through N and we will test each n for primality
while n <= N:
    factor = 2  # initial value of possible factor
    isPrime = True  # variable to remember if n is a prime or not
    factorUpperBound = math.sqrt(n)  # the largest possible factor we need to test is sqrt(n)

    # loop to generate and test all possible factors
    while (factor <= factorUpperBound):
        # test if n is evenly divisible by factor
        if (n % factor == 0):
            isPrime = False
            break

        factor = factor + 1

    # Output
    if isPrime:
        print(n)

    n = n + 1

今天，你学会了解决问题优化代码的思路了吗，今天你有什么收获吗？