本节书摘来自华章计算机《从问题到程序：用Python学编程和计算》一书中的第3章，第3.1节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
第3章
基本编程技术
第2章讨论了简单的计算和编程，展示了一些实例。通过对有关内容的学习，读者应该已经做了一些简单程序，对写程序和做计算有了些实际体会。虽然编程中细节较多，但也是很有趣的工作。为了完成一个程序，首先要分析问题、寻找解决方案，这些需要发挥人的聪明才智和想象力，也可能涉及一些相关领域的知识。要把设计变成可以运行的程序，既需要智力，也需要有条理的工作，一个小错误就可能使程序不能正确执行。当然，高度精确性也是现代社会对人的基本要求，写程序的过程能给我们许多有益的经验。
学习编程要经历一个过程，但这些并不表示这里的学习就是简单的经验积累，也不意味着只要多写程序就一定能把程序写好。人们通过多年的编程实践，总结出许多带有规律性的东西，总结出许多编程的模式、方法和技术，还进一步研究了许多理论问题。在学习编程时，一开始就应该注意前人的经验。正确的好程序不可能是随便写出来的，也不应该是修修补补凑出来的。只有认真学习怎样写好小程序，弄清其中的基本道理，才可能进一步写出更大更复杂的程序。这些都是本书希望特别强调的问题。
在进一步了解Python的其他功能之前，初学者需要更好地理解如何把已有基本知识应用于实际，这就是本章的目的。在三种基本的流程模式和相关语言结构中，顺序模式最简单，用复合语句描述也直截了当。使用选择模式，最重要的问题是正确描述条件，考虑不同情况下的动作，用条件语句实现也不困难。初学编程阶段的主要难点是重复执行模式。这种模式比较复杂，用循环语句实现时牵涉的问题较多，是本章讨论的第一个重点。
本章将首先讨论编写循环的一些基本技术，通过一批程序实例，展示一些典型的循环程序设计。这里的方式总是从分析问题开始，逐步发掘完成程序的线索，最终做出能解决问题的程序，以帮助读者看到“从问题到程序”的思维过程。对于一些问题实例，讨论中给出了能解决问题的多个不同程序，并特别讨论它们之间的差异及优缺点。这样做是希望读者理解：编程不是教条，也不应死记硬背。即使很典型的问题，也没有应该记住的标准解答。只要不是极端简单的问题，总有许多解决方法，可以写出许多形式或实质上或多或少不同的程序，而且它们往往各有长短。当然，也不能说这些程序都有同等价值。实际上，正确的程序也可能有优劣之分，讨论中也会对程序的评价提出一些看法。
在第2节里将介绍一种函数定义技术，称为递归定义，这种技术在处理一些问题时非常有效。最后一节讨论了定义函数的意义和相关的思考和设计问题。本章还将讨论一个非常重要的理论问题：程序的终止性。本章最后还将深入讨论定义函数的一些问题。
3.1 循环程序设计
前面说过，没有循环的程序都是平凡的程序。任何复杂一点的计算过程中必然会出现重复性的计算，需要用循环描述。本节集中讨论基于循环的编程问题。
3.1.1 循环的需求和问题
在程序里写循环，前提是我们发现计算过程中可能需要（或者应该使用）循环。在分析问题时，应该注意识别计算中需要重复执行的类似动作，这种情况说明可能需要引进一个循环，统一描述和处理计算中的一批类似工作。
需要循环的情况
需要写循环，常见情况如需要一批可以按统一规则计算的结果；需要对一系列类似数据做同样处理；需要反复从一个结果算出下一结果等。这些都属于重复性计算，如果重复次数较多，或者次数无法确定，就应考虑用循环。下面是一些典型情况：
1）需要多次执行类似操作而且操作次数较多，适合用循环处理。对这类情况，采用循环通常能缩短程序。用一段公共代码描述公共操作，更容易检查、维护和修改。
2）需要做一些重复性的操作，但在编程时无法确定操作的次数，结束条件由重复工作中数据的情况决定。这类情况就必须通过循环处理。
3）决定重复控制的因素来自函数的参数或程序的输入，也必须用循环描述。
举例来说，假设现在需要制作一个摄氏与华氏的温度对照表，要求从摄氏0度到200度，每5度一项。这就是典型的第一种情况。而前一章里通过牛顿迭代法，以不断改进猜测值的方式求平方根，就是典型的第二种情况。第2章里也给出了一些循环控制依赖于函数的参数或程序输入的例子。
写循环时需要考虑的问题
写循环的第一步是看到计算中需要做一些重复的操作，而且有规律可循，但从发现计算中的重复性动作，到写好一个循环结构，通常也不是直截了当的，还需考虑和解决许多具体问题，考虑问题的基础是计算中需要做什么。
首先弄清楚需要重复做的处理工作，根据它描述循环的主体。另一方面就是循环的控制，要确定怎样开始、怎样继续或停止循环。这里有许多具体问题，包括：
- 为了完成重复性计算，需要为循环引进哪些变量？用什么变量控制循环？
- 循环开始前，这些变量应该取什么值（初值问题）？
- 在循环体里（在一次迭代计算中），哪些变量应该更新，其值应该如何变化？
- 在什么条件下结束（或者继续）循环？
- 循环结束后，如何得到所需的结果？
这些都是本节讨论的重点。还有些具体问题，如需要确定用语言里的哪种结构实现循环等。如前所述，如果需要重复的次数和方式比较清晰，有可能通过一个循环变量和一个迭代器（如range）控制，就应该用for语句实现，因为它更简单清晰。如果写程序时不能确知循环的次数，或循环控制的方式比较复杂，就必须用while语句。
在实际编程中，应该采用最简单、最清晰的循环描述方式，首先考虑用for语句和向上循环（循环变量的值递增）。在这里还应该注意Python的整数范围描述方式及其意义。在Python语言里说“从m到n”时总是指序列m, ..., n-1，也就是数学的区间 [m, n)，左闭右开，包括m但不包括n。Python语言中描述迭代器的range(n)、range(m, n)、range(m, n, d)、描述字符串切片时的参数等，都采用左开右闭的描述方式。后面还会看到许多实例。我们在编程中也应尽可能采用同样的规则。
每个循环都有可能用多种不同的方式描述。举个简单例子，假设现实中要求对13到26的整数循环（实际要求是包括13和26）。显然可以用for循环实现，迭代器描述可以用range(13, 27)或者range(26, 12, -1)。按上面说法，如果没有其他需求，就应该用前者（向上循环）。这类简单情况一般不考虑while。另一个问题，假设需用while写一个循环，要求在变量的值大于20时结束，用n <= 20或n < 21作为条件都是正确的。但按照Python的习惯，人们赞成后者（左闭右开）。
浮点数与循环控制
由于浮点数计算是近似计算，基于浮点数描述循环控制，需要特别关注计算的不精确问题，否则，写出的循环很可能没有反映我们的需求。
首先，range要求一个到三个整数类型的（表达式）参数，不能用浮点数。由于这种规定，在进入用range控制的for语句时，循环的次数就由（当时的）迭代器确定了。在循环里给循环变量赋值不会改变循环的控制情况。例如：
for i in range(0, 10, 2):
print(i)
i -= 1还是会输出0、2、4、6、8。也就是说，在循环过程中，变量i一次次反复从迭代器得到值，每次得到的新值与当时i的值无关。
现在考虑用浮点数控制while循环的情况。用一个实际例子说明有关问题。
假设现在需要写一个函数，求sin (x2 + 1)·cos (x) 在 [0, 3] 区间的数值积分，也就是说，求出函数在这个区间的定积分的数值近似。根据高等数学的知识，可以用区间分割法求得这个近似值。现在考虑一种简单方法，把区间分为100份，基于每个区间左端点的值计算小矩形的面积，累积得到积分值。简单考虑可能写出下面程序：
from math import sin, cos
x = 0.0
value = 0.0
while x != 3.0:
value += sin(x * x + 1) * cos(x) * 0.03
x += 0.03
# 这时value的值应是所需结果这段程序直接反映了区间分割法的数学定义，循环做到x等于3.0结束。然而，如果把这段程序送给Python解释器，执行将陷入无穷循环。原因很简单：浮点数是近似计算，从0开始反复加0.03，加100次后结果通常不是3.0，继续加也不会等于3.0。
这个实例说明，不应该用浮点数的等于关系作为循环结束的依据，因为这样做没有任何保证。改用小于关系，就可以保证循环一定结束：
from math import sin, cos
x = 0.0
value = 0.0
while x < 3.0:
value += sin(x * x + 1) * cos(x) * 0.03
x += 0.03
print(value)这时程序能输出一个结果，但结果对不对呢？[ 具体结果对不对，是否为函数积分的近似值，请读者自己想办法验证（利用Python）。]
要想计算的结果合理，一个基本要求是循环正好做了100次。如果加入一个计数变量，并在循环体里将其加一，最后检查该变量的值，就会发现一个奇怪的情况：这个循环执行了101次，得到的结果显然不对。这里的原因也很简单：由于是近似计算，加100次的结果完全可能大于或小于0.03的100倍。如果仍然小于，就会多循环一次。这个例子说明，用浮点数控制循环的次数，没有准确而清晰的保证。
解决这类问题，还是应该回到用整数控制循环，下面是一种解决方法：
from math import sin, cos
value = 0.0
for n in range(100):
x = n * 0.03
value += sin(x * x + 1) * cos(x) * 0.03
print(value)由于整数计算没有误差，采用这种做法，既保证了正确的循环次数，又保证了所用的函数参数尽可能精确（不会积累舍入误差）。
上面例子反映了用浮点数控制循环的基本问题：计算不精确可能导致错过所考虑的精确值，累积误差可能导致循环控制的错误。总而言之，不应该基于浮点数去描述需要准确控制的循环过程。有些情况应该用浮点表达式控制循环，如前一章求平方根的函数所示，通常用于控制不断进展（逼近）的迭代，还要设置合理的允许误差。
3.1.2 常见循环形式
具体循环的情况千差万别，很难清晰地分类，但我们可以提出一些常见的类型。本节考虑几种典型的循环情况，供读者参考。但是，请不要把这里的分类看作教条，实际程序里的一个循环有可能属于这里的不止一个类型。
简单重复
需要重复地做一批类似的但又相互完全独立的工作，是可能用循环描述的最简单情况。如果这类工作的项数较多，用循环描述比较方便。如果要做的工作项数在编程时无法确定（例如，具体情况与输入有关，或者与函数的参数有关），就必须用循环描述。采用一个描述，除了可能缩短程序外，最大的优势是把有关处理问题集中到一处，便于设计、实现、调整和修改。如果需要，还可以把有关处理定义为函数，引进新的概念。
简单重复的特点就是需要对一批数据（或数据组）中的每一项做完全相同的计算，分别得到结果，并且分别使用。这样，同一循环的不同迭代之间相互无关，反映了原问题中不同工作相互无关的特性。例如，需要反复读入一批同类数据，对每个（或每组）数据分别处理，将得到的结果输出，或以同样方式保存。前一章示例中的温度转换、作业里的各种表格生成，都属于典型的简单重复计算。[ 以同样方式保存，可能牵涉到后面章节介绍的数据组合机制。]
这里的关键是计算或操作采用统一的模式，可以用同一段代码描述，不同计算之间的差异只是一个或几个变量的取值，而这些取值可以按同样的规律产生，或者按同样的方式获得。重复工作的识别和描述都比较简单，写好循环的关键是总结出共同的计算模式，确定循环中变量取值的变化规律。
下面的循环取自第2章的示例：
while True:
n = int(input("Next int:"))
if n < 0:
break
print("Factorial of", n, "is", fact(n))它基于用户输入的整数，计算阶乘并输出，其中的数据统一通过输入获得，主要计算都调用同一个函数完成，输出的方式和形式相同，是典型的简单重复模式。另一方面，由于结束条件是根据用户输入确定的，编程时不知道具体循环次数，应该用while结构。
实际上，交互式方式下Python解释器的最高层就是一个简单重复计算：反复读入人的输入（表达式或语句），执行命令，最后输出计算的结果。一般交互式程序的最高层也都是这样，差异只在于输入的形式、功能和计算的实现方式不同。
累积
另一类典型的计算工作是累积，其特点就是在重复性的工作中用一个或几个变量不断积累信息。这里的重复表现为获得有关信息的方式类似，将得到的信息积累到变量里的方式相同。很显然，这种工作适合用循环描述，这种循环可称为累积循环。在这种循环中用于积累信息的变量可称为累积变量。
显然，要想在循环的一次次迭代中不断将信息“记入”累积变量中，在循环开始之前，所用的变量就应该有定义，而且针对具体的累积方式设置好初始值。循环的每次迭代中把一些数据的信息累积到变量里，更新变量的值。作为累积，所赋新值应包含变量原值的信息。而（这些）变量的最终值也就是循环的主要结果，在循环结束后使用。
在与数值有关的计算中，累积中常用的操作如 + 或 ，典型操作如x = x + e，其中e为某个表达式，这类赋值最适合用扩展赋值运算符 +=、= 等描述。这样写，既能使描述简洁，也更好地表现了基于变量原值计算并更新的事实。更一般的累积情况需要特殊的方式，可以考虑定义一个专门的累积函数g，用x = g(x, e)描述更新。
下面看几个累积程序（片段、函数等）的实例。
实际上，在前一章里已经展示过一些累积循环，例如求阶乘函数，其主体就是一个典型的累积循环（现在改用扩展赋值运算符描述）：
def fact(n):
prod = 1
for k in range(2, n+1):
prod *= k
return prod这里的累积变量（只有一个）是prod，循环前设置其初值为1，在循环中不断乘以由循环变量k提供的值（统一更新方式），其最终值就是本函数的结果。
注意，对于累积变量，其初值通常都与循环中的更新方式有关。如果更新采用 +=，相应变量的初值通常总是0，如果更新用 *=，相应变量的初值通常是1。也就是说，按数学中的说法，变量的初值常用更新运算的单位元。
现在考虑数项级数中前n项的计算。例如，数学中有下面公式：
现在考虑定义一个函数计算前num项的值。将循环中的累积变量命名为ln2，由于是求和，其初值取0。相应的循环比较规范，通项可以通过一个取值为1到num（包括num）的循环变量n计算，因此可以用for循环实现。
最后一个问题是通项的符号，可以直接用表达式(-1)**(n-1)计算，进一步写出程序已经很简单了。但采用这种做法，每个通项都要进行上述乘幂运算，实际上做了很多乘法。能不能减少这种乘法？可以注意到，这个通项中的下一项的符号总与前一项相反，如果知道当前项的符号，将其乘以-1就得到了下一项的符号。这也是一种信息的累积。
引入另一个累积变量sign，可以写出下面的函数定义：
def ln_2(num):
ln2 = 0.0
sign = 1
for n in range(1, num + 1):
ln2 += sign * 1/n
sign *= -1
return ln2
for i in range(100, 200, 10):
print("First", i, "term of series for ln 2:", ln_2(i))最后的循环是做试验，程序执行中将输出：
First 100 term of series for ln 2: 0.688172179310195
First 110 term of series for ln 2: 0.6886223863178897
First 120 term of series for ln 2: 0.688997874401657
First 130 term of series for ln 2: 0.6893158191755918
First 140 term of series for ln 2: 0.6895885067652056
First 150 term of series for ln 2: 0.6898249580908314
First 160 term of series for ln 2: 0.6900319459942255
First 170 term of series for ln 2: 0.6902146544587359
First 180 term of series for ln 2: 0.690377118712483
First 190 term of series for ln 2: 0.6905225267244215函数以很慢的速度逼近正确值0.693147180559945……。
在实际的计算中，累积工作也可能还有条件，只有满足条件的数据才应该累积。此时，就需要在实现这种计算过程的循环中加入条件判断，只在数据满足条件时才更新累积变量。实际上，这是一类很重要的计算模式，称为生成和筛选。一般情况是，以某种统一的方式不断获得（或者直接枚举出，或者生成、计算出）一些数据，然后用一个筛选条件检查，只将满足条件的数据“记入”累积变量。
下面是一个简单实例。现在希望求出1000以内所有除以7余数为2的数中不能整除3的整数之和。下面的简单循环能实现这一计算：
sum = 0
for i in range(1, 1001):
if i % 7 == 2 and i mod 3 != 0:
sum += i再如，下面程序片段将求出用户输入的前10个偶数之和：
sum = 0
n = 0
while True:
x = int(input("Next integer: "))
if x % 2 == 0:
sum += x
n += 1
if n == 10:
break这里的数据来自用户输入，程序里用另一个累积变量（计数变量）n记录已求和的数据项数，其值达到10就结束。循环结束后，变量sum的值即为所需。从这个程序里，还可以看到一些新情况：break语句可以嵌套在循环里任意深的条件结构中，在复杂的条件下退出循环。无论结构多复杂，break总是退出最内层循环。
最后这两个例子反映了生成和筛选模式的共性情况：循环体中包含一个生成部分，每次产生一项候选数据；而后有一个筛选部分，从得到的数据中选出满足条件的合格数据。有一些实际情况，其中很难直接生成所需要的数据（数据序列），这时可以考虑找一种较为简单的生成方式，得到一个更大的数据序列，再从中选出实际需要的数据。
递推
递推是一种更一般的循环计算模式，在循环的每次迭代中，基于某个（或者某些）变量的当前值，按某种特定方式算出该变量的下一个值。在实现递推的循环中，循环体里总有一个或者一组语句实现如下形式的计算：
d = f(d, ...)也就是说，变量d的下一个值需要通过d本身（和其他数据），利用某种方法计算出来。这种操作实现从d的现值推出其下一个值。这种d也称为递推变量。实际上，累积也可以看成一种简单而且规范的递推，其计算规则简单而直接。
递推变量也需要初值，必须在循环之前给定。有时在一个循环中有可能有多个递推变量，它们相互扶持、同步前进。某个或某些递推变量的最终值就是需要的结果。要写好一个递推循环，需要做几件事情：
- 选定循环中使用的递推变量；
- 确定这个（这些）递推变量的初值；
- 确定如何从已知信息（包括递推变量的当前值）计算出各个递推变量的下一个值的方法，用程序语句实现相关计算。
第2章中求x平方根的程序包含一个典型的递推循环。递推变量guess以1.0作为初值，通过不断应用迭代规则推出下一个猜测值，最终得到一个满意的近似值。下面修改过的函数能显示出递推的收敛情况：
def sqrt(x):
guess = 1.0
n = 0
while abs(guess * guess - x) > 1e-8:
guess = (guess + x/guess)/2
n = n + 1
print(str(n) + "th iteration:", guess)
return guess求sin函数的值
考虑函数sin的计算，数学家提出了下面无穷级数：
现在考虑用这个公式计算sin函数的近似值，要求算到级数项的绝对值小于1e-6。
由于级数项的结构比较复杂，可以考虑定义一个独立的函数计算它。再根据上述级数定义计算sin的函数，程序写出如下：
def term(x, n):
t = (-1)**n * x ** (2 * n + 1)
for i in range(2, 2 * n + 2):
t /= i
return t
def mysin(x): # 自己定义的计算sin的函数
sn = 0.0
n = 0
while True:
t = term(x, n)
if abs(t) < 1e-6:
return sn
sn += t
n += 1函数term里的循环实现除以 (2n+1)!的计算。我们不希望在函数mysin里两次计算同一个项，这里采用先算出项值存入变量，而后检查和使用的方法。通过几个常见值的计算，可以看到这个函数定义应该没错：
>>> mysin(0.0)
0.0
>>> mysin(pi/2)
0.999999943741051
>>> mysin(pi)
-7.727858895417119e-07仔细思考上面程序实现的计算过程，其中最重要的部分就是反复算出一个个项的值。可以想到，这里级数项的计算中出现了许多重复计算：在后一项的计算中，大部分工作都是计算前一项时已经做过的。不难写出级数项之间的递推关系：
级数的首项是x，根据递推公式可以算出随后的各项。
把这个递推关系融合到mysin的定义里，修改后的函数定义如下：
def mysin(x):
sn = x
t = x
n = 0
while True:
n += 1
t *= - x * x / (2*n) / (2*n + 1)
if abs(t) < 1e-6:
return sn
sn += t通过检查运行，可以看到这个函数得到的结果与前一个定义相同。在这个函数的执行中避免了大量重复工作，这件事在实践中非常重要。
有趣的是，做更多的试验却可能发现问题：
>>> mysin(10*pi)
0.00034023652139616377
>>> mysin(20*pi)
-4562371877.727803用更大的值计算，情况更甚。数学上的sin是周期函数，上面计算的正确结果都应该是0，但为什么会出现误差越来越大的情况？对20π的计算结果已经毫无意义了，但为什么会出现这种情况？罪魁祸首应该是计算误差，但误差为什么会积累到这种程度？请读者仔细分析这两个表达式的计算过程（提示：请考虑利用Python做些试验）。
要解决上述问题，一种可能方法是用数学包里的fmod函数对参数规范化，因为sin (x) = sin +(x + 2nπ)，可以先把实参归结到 [0, 2π] 的范围内。修改后的定义如下：
from math import fmod, pi
def mysin(x):
x = fmod(x, 2*pi)
sn = x
t = x
n = 0
while True:
n += 1
t *= - x * x / (2*n) / (2*n + 1)
if abs(t) < 1e-6:
return sn
sn += t下面是几个计算实例：
>>> mysin(100*pi + pi/2)
0.999999943741051
>>> mysin(-pi/2)
-0.999999943741051
>>> mysin(-pi)
7.727858895155385e-07可以看到，上面的问题不再出现了。
这个例子反映出几个问题：
- 程序完成后的测试必须比较充分，不仅应该包括最简单的数据实例（如前面的0，pi/2，pi等），还要选择一些不那么常规，但也可能出现的数据实例。
- 在浮点数计算中，误差的积累有可能使结果完全失去价值。对于实际程序里与浮点数有关的部分，必须针对可能情况做充分的测试。
- 选择测试实例，应该找那些容易判断结果正误，但又能反映测试需要的实例。
判断素数
素数是非常重要的基本数学概念：如果一个大于1的自然数除了1和其自身以外没有其他因子（没有真因子），它就被称为素数（或者质数）。
自然数n的因子，就是能整除n的正整数。而所谓k整除n，也就是说n除以k的余数为0。在Python里，这一条件可以用表达式n % k == 0描述。
根据上面定义，可以直接得到一种朴素的素数判断方法：对给定的自然数n，取从2开始的一些整数，逐个检查它们是否为n的因子。如果发现了n的真因子，那么n就不是素数。如果一直没有发现真因子，而且做的试验已经足够多，已经能确定n不可能有真因子, 就可以结束检查并断定n是素数。
要实现这个判定方法，可以用循环描述检查的过程。循环中从2开始检查，最简单的方法是从小到大检查每一个整数。采用这种做法，剩下的问题就是检查到什么时候结束？
从2一直检查到n肯定可以做出正确判断，但稍微考虑就能看到一个事实：如果n有真因子，那么它一定有小于等于n的平方根的真因子（请读者自己证明这个结论）。这样，检查循环只需进行到等于或者超过了n的平方根。[ 显然，这样的检查过程中会做很多不必要的工作，但都比较简单。改变检查的方式可能需要存储一些信息，需要有更高级的数据设施。后面还会讨论这个例子。]
基于上面考虑定义出的判断函数（谓词）is_prime如下：
def is_prime(n):
if n < 2:
return False
k = 2
while k * k <= n:
if n % k == 0:
return False
k += 1
return True术语谓词是指返回逻辑值（真假值）的函数，它们通常用于完成程序中的判断，经常被用在条件语句或者循环语句的头部。
基于函数is_prime，很容易写出一个程序，检查一定范围内的偶数，看看哥德巴赫猜想是否成立。例如下面循环检查直至200的偶数：[ 哥德巴赫猜想是数论中的著名猜想，它断言：任何一个大于等于6的偶数都可以分解为两个奇素数之和。我国数学家，特别是陈景润，在有关哥德巴赫猜想的研究中取得了举世瞩目的成果。但是，这个猜想至今还没有被证明或证伪。]
for n in range(6, 201, 2):
for i in range(1, n//2 + 1, 2):
if is_prime(i) and is_prime(n - i):
print(n, "=", i, "+", n-i)
break请读者通过试验考察前面素数判断函数的工作效率。不难看到，随着整数值的增大，该函数得到结果的时间越来越长。这件事很自然，例如，对于一个100位的整数，用上面函数判断，过程中需要检查1050个数，显然太耗费时间了。
在有关数论的研究中取得了很多与素数有关的成果，其中一些成果有可能用于素数判断。基于有关成果，人们提出了一些不同的算法。在网上可以搜索到许多情况。建议读者自己找到一些有趣的算法，也可以自己实现一下，作为编程练习。
最近对于素数判断有一个重要进展，2002年印度科学家提出了一个新算法，用发明者的名字首字母缩写命名，称为AKS算法。该算法在理论上优于已有其他算法。
素数判断在许多计算领域中有重要的应用，特别是在密码和安全领域。素数问题及其算法已经成为今天计算机和信息系统安全的基础。
3.1.3 输入循环
与输入有关的循环是程序里的一类常见循环。在这种循环中，程序不断从外部获得数据，并将其用于内部的计算，得到了足够多的数据后结束循环，继续进行循环之后的工作。考虑这类循环的控制和结束，可以看到下面两种典型情况：
- 在编程时已经明确知道需要输入的数据的项数情况。循环中只需一项项读入数据，完成输入后结束。这种输入循环完全由程序内部控制，是最简单的循环输入情况，相关编程中没有新问题。当然，这种循环输入也存在一些变形，见下。
- 编程时只知道需要从外部输入一批数据，但并不确知输入数据的具体项数。前面说过，这种情况只能通过循环描述。这里的新问题是如何确定循环应该结束。显然程序执行中应该反复循环，直到使用者认为应该结束的时刻。也就是说，这是一种由程序外部控制的输入循环，应称为由输入控制的循环。
下面分别讨论与输入有关的这两类循环。
简单输入循环
简单输入循环完全由程序内部确定，这种方式适合在写程序时就能确定方式的循环。当然，具体方式需要根据实际情况来设计。
例如：假设现在要求获得一年中各月的降雨量数据，求出全年的降雨量。显然，这个计算需要正好12项数据。假设数据由用户通过键盘输入，下面程序段能解决这个问题：[ 实际中可能是由其他来源取得数据，例如数据来自已经存在于计算机系统里数据文件，或者来源于网络。虽然获取数据的方式可能不同，但所需循环的形式相同。]
print("Calculating year's rainfall")
rainfall = 0.0
for i in range(12):
x = float(input("Rainfall of a month: "))
rainfall += x
print("The total amount of the year", rainfall)对于这类简单循环，体代码段的重复执行次数事先已知，原则上说，完全可以将其展开，用该段代码的一串拷贝实现同样功能。用循环描述只是使代码大大简化，写起来也更方便。此外，在这种循环里，输入只作为信息源，没有扮演任何特殊角色。
此类简单循环也有一些可能的扩充方式。一类典型问题是需要从输入中筛选出“合格”数据，换句话说，假定实际输入中只有一部分数据满足要求，处理过程中需要把“不合格”的数据筛选丢掉。看一个例子。
【例】假定需要输入一系列数值，求出其中前10项非负数据的平均值。
首先，问题描述已经说明了输入中可能出现数据为负的情况，而且负数是无用数据，在考虑平均值时应该丢弃。进一步说，虽然程序要求处理10项数据，实际输入数据的项数却不可知。还有，在同一程序的不同运行中，需要实际输入的数据项数可能不同。这些情况说明两点：首先，这个程序必须用循环实现；其次，for语句不能处理这种情况，只能用while循环，而且需要自己记录实际获得的有效数据项数。
把上述问题都考虑清楚后，可以很自然地写出下面的程序：
print("Calculate average of 10 input positives.")
sum0 = 0.0
num = 0
while num < 10:
x = float(input("Next number: "))
if x > 0:
sum0 += x
num += 1
print("Average of 10 positives:", sum0 / num)这里有一个问题值得提出：最后一个语句里写的是sum0 / num，写成sum0 / 10好不好？显然，对于所给的问题，这两种写法都能得到正确结果。但如果把这个num改为10，程序里就出现了两个10，而且它们必须保持一致。如果问题需求有变化，实际情况要求处理12项（而不是10项）数据，我们就必须把这两个10统一改为12。少改一个程序就错了（逻辑错误），而且不会有任何错误信息。这是很危险的。采用上面程序里的做法，需求变动时，只需要做一处修改，循环结束时总能得到正确的平均值。
细心的读者可能注意到另一个情况：程序里的两个输出字符串中也有10的信息。这件事也可以解决，请读者自己设法修改上面程序。
输入控制的循环
现在考虑另一种常见情况：需要以某种方式统一处理用户输入的一批数据，但并不知道用户将提供多少项数据。显然，这种情况只能通过循环，在反复执行中处理输入。但是，如何控制循环的执行和结束，还是一个需要解决的问题。
这里的情况意味着输入提供方（用户）可以输入任意多项数据，可以自由决定在任何时刻结束输入。在这种情况下，显然，处理输入的程序不能自行决定结束循环，只能被动地接受用户决定。而另一方面，用户希望结束的意图也只能通过输入传给程序。这就意味着我们需要为用户提供一种表达实际数据结束的方式，而且必须采用某种特殊的输入形式。这样安排之后，程序在运行中不断读入并检查得到的数据，区分两种情况：确定是正常输入时按正常方式处理，一旦遇到表示结束的特殊输入就结束循环。
这种循环的模式应该是：
while True:
data = input(…)
if data是表示结束的特殊输入:
break
正常输入的处理如果一个程序在运行中不断与使用者交换信息，它就是我们一再说到的交互式程序。使用者启动这种程序之后，程序将反复向使用者要求信息。如果得到符合需要的数据，它就完成一定的工作，而后重复这种循环，直至遇到某种预先确定应该结束的情况。显然，交互式程序中通常都会有一个或多个输入循环，可以是内部控制的输入循环，也可以是输入控制的循环。任何输入控制的循环都需要确定一个表示结束的特殊输入。
这种表示正常输入结束的特殊输入（特殊命令），实际上是程序与使用者之间的一种约定。使用者需要知道这种约定，藉此表达他们的输入结束要求。程序也知道（并处理）这种约定，遇到结束信号时就结束循环。作为编程者，需要设计这种约定，在程序里加入对它的检查，并且告知程序的使用者。这种约定是程序使用方式的重要组成部分。作为一个具体例子，如果在Python IDLE的交互状态下调用函数quit()或者exit()，Python解释器的交互窗口就会结束执行。这就是IDLE（的设计者）与我们的约定。
为实现一个具体的这种循环，我们必须设定一种具体约定。显然，任何正常（正确）的输入数据都不能作为结束循环的信号。例如，对于一个要求输入一串整数的程序，我们不能用0作为结束循环的特殊输入；但如果程序要求的是一串正整数，用0或者负数作为结束信号就都是合理的设计。如果程序的功能是对一系列输入数值做一些统计工作，例如求它们的平均值和其他统计计算，那么任何合乎Python对数值转换要求的输入都是合法数据，因此不能以数值判断作为结束判断。Python的input函数返回输入串，要求程序做转换。因此这时就可以考虑用其他形式的字符串作为结束标志，例如：
while True:
item = input("...")
if item == "end":
break
data = float(item)
正常输入的处理这样写程序，也就是约定用字符串end作为结束标志。为方便用户，提示符串可以考虑用 "Please give next number, 'end' to finish."。相应程序可以写出如下：
print("Calculating average.")
ss = 0.0
n = 0
while True:
snum = input("Next number ('end' to stop): ")
if snum == "end":
break
ss += float(snum)
n += 1
print("The average of these " + str(n) + " numbers is", ss/n)下面是另一个简单的实例：
name = ""
while name != "no more":
name = input("Hi, friend! What is your name? ")
print("Hello, " + name + "!\n")这个循环要求输入是字符串，用特殊字符串no more表示不再有更多人名输入了。最后的输出语句里用到字符串拼接，是为了做出符合需要的输出形式，避免多个输出项之间不必要的空格。注意，这里假设了用户的输入是人名，而人名就是字符串。由于编程时选定的结束约定，如果有个人名叫no more，程序就无法对其表达问候了。
为避免表示结束的字符串不能正常处理的问题，可以考虑另外安排一个输入，专门处理有关结束的字符串。例如，把前面程序改为：
while True:
name = input("Hi, friend! What is your name? ")
print("Hello, " + name + "!\n")
yesno = input("Next? (Yes/No): ")
if yesno == "No":
break在这个循环里，实际数据和控制循环的输入是分开考虑的。
在实际应用中，输入未必是字符串，可以是任何数据，甚至可以是若干数据项的组合。另一方面，处理数据的操作也可以任意复杂。上面两个例子展示了最常用的两种控制方式：或者是基于数据输入自身，或是引入专用于控制是否继续的输入。
正如前面的脚注所言，实际程序可能有不同的输入源。例如程序的输入可能来自文件，或者来自网络，这些输入也经常需要通过循环处理。虽然输入源可能不同，但都会遇到上面讨论的问题，都需要有表示输入结束的约定和相应处理。后面第6章将讨论从文件输入的问题，届时会看到一些情况。
