2.2 循环控制
循环控制是在特定的条件下，重复执行一些操作。例如，求和式
，可以用 if 语句和goto语句构成循环计算，程序如下：
s = 0; i = 1;
loop:
if (i <= 100)
{ s+=i;
i ++;
goto loop;
}
程序流程从一个控制点返回前面语句序列的一个入口重复执行，这种执行流程称为循环控制。循环是十分常用程序结构，所有高级语言都提供相应的结构化语句代替goto语句实现循环控制。
C++的循环控制语句有：while语句、do_while语句和for 语句。如果用while语句写求和的算法，则程序可以写为：
s = 0; i = 1;
while (i <= 100)
{ s+=i;
i ++;
}
循环语句自动实现判断和跳转。在循环语句中，重复执行的操作称为循环体，执行重复操作的条件称为循环条件或循环控制条件。
2.2.1 while语句
while 语句是最基本的循环语句，在程序中常用于根据条件执行操作而不需关心循环次数的情况。
1.while语句的形式和执行流程
while语句形式为：
while（表达式）
循环体 ；
其中，“表达式”为循环控制条件，一般为逻辑表达式，从语法上讲，也可以是其他表达式，其值视为逻辑值。“循环体”可以是简单语句，也可以是复合语句，用于描述重复计算、处理的一系列操作。
while语句表示当“表达式”的值为true时，重复执行“循环体”的语句。while 循环又称为当型循环。执行流程如图 2.4所示。
图2.4 while语句的执行流程
从while 语句的执行流程，我们可以看到它有以下两个特点：
① 若条件表达式的值一开始为false（0），则循环体一次也不执行。
② 若“表达式”的值为 true（非 0），则不断执行循环体。要正常结束循环，循环体内应该有修改循环条件的语句，或其他终止循环的语句。
【例2-11】计算输入的所有大于0的整型数据之和。若输入负数，则结束程序的运行。
#include<iostream>
using namespace std;
int main()
{ int a,sum=0;
cin>>a; //输入第一个数据，建立循环条件
while(a>0) //a>0时执行循环
{ sum+=a; //累加a的值
cin>>a; //输入一个新的a值
}
cout<<"sum="<<sum<<endl; //输出累加结果
}
程序在说明变量sum时初始化为0。运行程序后，通过键盘输入a 的值，执行while语句。如果a>0，满足循环条件，则执行循环体内的语句：
sum+=a; //累加a的值
cin>>a; //输入一个新的a值
然后控制返回while，判断a的值是否大于0，若为真，则重复执行循环体；直到a等于或小于0时结束。执行流程如图2.5所示。
图2.5 例2-11的执行流程
从前面分析可知，条件表达式a>0用来控制循环是否继续。变量a的值直接影响a>0的值。通常，把能够影响循环条件的变量称为循环控制变量。在一个 while 语句中，循环控制变量可以有一个或多个，这需要根据实际情况决定。
一般循环结构包括3个部分：循环的初始化、循环条件和循环体。循环体内通常有一个或多个用于改变循环控制变量的语句，最终使得条件表达式的值为false（0）从而结束循环。
在上面的例程中，在while之前对sum的赋值和输入a的值，是循环初始化部分；a>0 为循环条件表达式；循环体是一个复合语句。循环体内输入a的语句既用于接收新的数据，又用于修改循环控制条件。若输入的值小于或等于0，则表达式a>0的值为0，循环结束。
建立循环结构时要注意：
① 设计正确的算法及合理的操作顺序；
② 正确选取循环控制变量，设置相关变量的初值；
③ 循环体内一般要包含改变循环控制变量的语句，或其他转向语句，使循环能够正常结束。
例如，以下程序段：
i=0; //错误，乘法器初值为0
s = 0;
while (i <= 100)
{ i*=2;
s += i;
}
由于乘法器i的初始值被赋予0，循环体内表达式i*=2 无法使i增加，以致循环控制表达式i<=100的值永真，不能结束循环。这就是通常说的“死循环”。
2.应用举例
【例2-12】输入一串字符，以“？”号结束，输出其中的字母个数和数字个数。
解决这个问题的算法是：设置两个计数器，分别用于统计字母和数字的个数。输入和统计都是重复性的工作，可以用循环结构实现。字母字符、数字字符的ASCII码值是连续的，可以很轻易地使用条件语句判断。每输入一个字符，如果不是“？”号，就判别它是否为字母，若为字母，则字母计数器累加 1；否则，再判别是否为数字，若为数字，则数字计数器累加 1。重复上述工作，一直到输入的字符为“？”后结束。最后输出字母和数字的个数。
程序中用变量ch存放当前输入的字符，nl为统计字母个数的计数器，ng为统计数字个数的计数器。按上述算法编写程序如下：
#include <iostream>
using namespace std;
int main()
{ int nl=0,ng=0;
char ch;
cin.get(ch); //输入第一个字符，建立循环条件
while(ch!='?') //循环条件为ch!='?'
{ if(ch>='a'&&ch<='z'||ch>='A'&&ch<='Z') ++nl;
else if(ch>='0'&&ch<='9') ++ng;
cin.get(ch); //输入后续字符
}
cout<<"\nnl="<<nl<<" ng="<<ng<<'\n';
}
运行程序，输入数据和输出结果如下：
Is the password 123456 ?
nl=13 ng=6
cin.get(ch)的作用是获取一个当前输入字符并写入变量ch中。iostream的get函数能够接收任何字符，包括空格、回车等。这与采用输入运算符cin>>不同。cin>>会自动把空格和控制符作为输入界符，结束一个变量的输入。
【例2-13】给定两个正整数，求出它们的最大公约数。
求最大公约数有不同的算法，其中速度较快的是辗转相除法。该算法说明如下：
若m和n为两个正整数，则有：
当m>n，m与n的最大公约数等于n与m%n的最大公约数；
当n=0，m与n的最大公约数等于m。
程序中，用变量a存放被除数（初始值是m）；变量b存放除数（初始值是n）；变量r用于存放a、b相除的余数。算法可以描述为：
while (r != 0)
{ 把a%b的值赋给r ；
用b的值替换a的值；
用r的值替换b的值；
}
循环结束后，a的值就是m与n的最大公约数。
辗转相除法求最大公约数的程序如下：
#include <iostream>
using namespace std;
int main()
{ int m,n,a,b,r;
cout << "input two integers :\n";
cout<<"?"; cin>>m; //输入第一个正整数
cout<<"?"; cin>>n; //输入第二个正整数
if(m>n) {a=m;b=n;} //把大数放在a中，小数放在b中
else {a=n;b=m;}
r=b; //置余数初值
while(r!=0) //当余数不等于0时执行
{ r=a%b; //求余数r
a=b; //用b的值替换a的值
b=r; //用r的值替换b的值
}
cout<<m<<" and "<<n<<" maximal common divisor is : "<<a<<endl;
}
运行程序，输入数据和输出结果如下：
input two integers:
？ 24
？ 16
24 and 16 maximal common divisor is : 8
2.2.2 do_while语句
do_while语句是while语句的变形。它们的区别在于，while语句把循环条件判断放在循环体执行之前，而do_while语句把循环条件判断放在循环体执行之后。
1.do_while语句的形式和执行流程
do_while语句形式为：
do
循环体
while（表达式）
其中，“循环体”和“表达式”与while语句的意义相同。
do_while语句的含义为，重复执行“循环体”的语句，直到“表达式”的值为 0（假）结束。do_while 循环又称为直到型循环。执行流程如图2.6所示。
图2.6 do_while语句执行流程
从 do_while 语句的执行流程可以看到，不管循环条件是否成立，它都至少执行一次循环体。
例如，求和式
的程序用do_while语句可以写为：
s = 0; i = 1;
do
{ s+=i;
i ++;
} while(i <= 100);
在一般情况下，while语句和do_while语句可以互换使用。
2.应用举例
【例 2-14】使用公式
求π的近似值，直到最后一项的绝对值小于10-12为止。
先求出右边和式的值，然后求π的值。求和式可以用循环实现。第i项的值等于1/(i*i)，循环体中对当前项计算并进行累加。因为当i→∞，有1/i2 →0，所以可以用一个被认为可以接受的精度值终止计算。
程序中的sum为累加器，i为计数器，变量term存放当前项的值，变量pi存放π的近似值。程序执行流程如图2.7所示。
图2.7 例2-14的执行流程
#include <iostream>
using namespace std;
#include <cmath>
int main()
{ long int i;
double sum, term, pi;
sum=1; i=1;
do
{ i+=1; //计数器
term=1.0/(i*i); //计算当前项
sum+=term; //累加
}while(term>=1.0e-12); //精度判断
pi = sqrt(sum * 6);
cout << "pi = " << pi << endl;
}
运行程序，结果为：
pi = 3.14157
【例2-15】输入用一个二进制数表示的正整数，转换成十进制整数输出。
在一般情况下，C++的键盘输入可以识别十进制数、八进制数和十六进制数，因此，输入二进制数据要作为字符序列处理。二进制数只包含0和1两个数字，输入时，先略去前导空格等非0、1字符，然后逐个字符读入处理，最后输入任意一个非0、1字符作为输入结束符。
把二进制数bnbn-1…b2b 1b 0转换为十进制数Dec的公式如下：
Dec=bn×2n+bn-1×2n-1+…+b2×22+b1×21+b0×20
用户从高位到低位输入二进制位串，程序可以采用移位方式处理数据，每读入一个位值，就把变量Dec中存放的数据乘以2，然后累加当前输入值。
程序如下：
#include <iostream>
using namespace std;
int main()
{ int Dec=0;
char ch;
cout << "Binary = ";
do //略去前导符号，直至ch存放第一个合法数字
{ cin.get(ch);
} while(ch !='0' && ch != '1');
do //循环，逐位转换
{ Dec+=ch-'0'; //把字符转换为数字，累加
cin.get(ch); //读入一位
if(ch=='0'||ch=='1') //如果是0或1
Dec*=2; //已经转换的数据左移一位
}while(ch=='0'||ch=='1'); //读入非0，非1字符时结束循环
cout<<"Decimal="<<Dec<<'\n'; //输出转换结果
}
运行程序，输入数据和输出结果如下：
Binary = 101101
Decimal = 45
【例2-16】用牛顿迭代法求解方程f(x)=x3+2x2+10x-20=0 在x0=0附近的根。
由数值计算方法可以知道，牛顿迭代公式为：
xn+1=xn- f(xn)/f′(xn) (n=0,1,2, )…
由题目，有：
f(x)=x 3+2x2+10x-20，f'(x)=3x2+4x+10
根据上述公式，计算过程如下。
① 令n=0，任意给定一个x0值，由迭代公式求得x1=x0- f(x0)/ f′(x0)，判别|x1-x0|是否小于给定精度ε。若小于，则迭代结束，x1作为方程的近似根；否则，执行下一步。
② 令n=1，由迭代公式得 x 2 =x1- f(x1)/ f′(x1)，然后判别|x2-x1|是否小ε。若小于，则迭代结束，x2 作为方程的近似根；否则，由x2计算出x3的值。
如此迭代，一直到|xi+1-xi|＜ε（i = 0, 1, 2…）为止。
由于每一步当前值只需用前两次迭代值xi+1和xi进行计算，因此在编程时只需x0和x两个变量来存放前两次迭代值。编写程序如下：
#include <iostream>
using namespace std;
#include <cmath>
int main()
{ double x0,x,epson;
cout<<"Input test root, x0 = ";
cin>>x0; //输入迭代初值
cout<<"Input precision, epson = ";
cin>>epson; //输入精度
do //循环
{ x=x0; //迭代
x0=x-(pow(x,3)+2*pow(x,2)+10*x-20)/(3*pow(x,2)+4*x+10); //求新值
}while(fabs(x0-x)>epson); //判断精度
cout<<"The root is : "<<x0<<endl; //输出近似根
}
运行程序，输入数据和输出结果如下：
Input test root, x0 = 1
Input precision, epson = 1e-12
The root is : 1.36881
本程序调用了两个标准库函数，它们均在头文件cmath中声明。
计算xy，求幂函数的函数原型为：
double pow(double x, double y);
求x的绝对值的函数原型为：
double fabs(double x);
【例2-17】从键盘上输入x的值，并用以下公式计算sin x的值。要求最后一项的绝对值小于10-8。
sinx的值可以调用库函数直接求出，但是，对该问题的分析，有助于进一步掌握循环结构程序的组织。
这是一个级数求和问题。可以对和式中的每项分别计算，计算出一项就累加一项，直到某项的绝对值小于10-8时为止。
还有一种高效率的计算方式。仔细分析式中每一项和前一项之间的关系，例如：
可以得到一个递推公式，设前一项为tn，当前项为tn+2，则有：
tn+2 = tn (- x2 / ((n-1) × n)) n = 3, 5, 7 …
按上述分析，编写程序如下：
#include <iostream>
using namespace std;
#include <cmath>
int main()
{ long int n;
double x, term, sum;
cout << "x = ";
cin>>x; //输入x的值
n=1; //置计数器初值
sum=x; //置累加器初值
term=x; //当前项
do //循环
{ n+=2; //计数器+2
term*=(-x*x)/(n-1)/n; //当前项的值
sum+=term; //当前累加和
}while(fabs(term)>=1e-8); //精度判断
cout<<"sin("<<x<<")="<<sum<<endl; //输出计算结果
}
程序中，变量sum为累加器，用来存放sin x的值，变量term 用来存放和式中的某一项，n表示某一项中x的幂。
2.2.3 for语句
在一般程序设计语言中，for语句用于确定执行次数的循环结构，但在C++语言中，for语句是最灵活的一种循环语句。它不仅可以用于次数循环，即能够确定循环次数的情况，也可以用于条件循环，即循环次数不确定的情况。
1.for语句的一般形式和执行流程
for语句的一般形式为：
for（[表达式 1 ]; [表达式 2 ]; [表达式 3 ]）
循环体;
其中，“表达式 1”、“表达式 2”和“表达式 3”都可以省略。
“表达式 1”不是循环体的执行部分，它仅在进入循环之前被执行一次。通常用于循环控制变量的初始化，所以也称为初始化表达式。
“表达式 2”是循环控制表达式。其值为true（非0）时执行循环，为false（0）时结束循环。
“表达式 3”在“循环体”执行之后执行，可以看做循环体的最后一个执行语句。通常用于修改循环控制变量。
for语句的执行流程如图2.8所示。
从for 语句的执行过程可以看到，它实际上等效于：
表达式 1 ；
while（表达式 2）
{ 循环体;
表达式 3;
}
因此，for循环可以作为次数型循环结构。次数型循环结构包括4个部分：表达式1、表达式 2、表达式 3和循环体。
例如，求和式
用for语句编写的程序如下：
s = 0;
for (i=1; i <= 100; i ++)
s + = i;
for循环在这里的功能是控制次数的循环。由for语句给循环变量i赋初值，判断循环条件，并修改循环变量的值。在循环体中，使用循环变量i的值进行累加。程序流程如图2.9所示。
图2.8 for语句的执行流程
图2.9 用for循环求和
2.for语句中的表达式使用
（1）for语句中省略“表达式”时，分号不能省略。当省略全部表达式时，for仅有循环跳转功能。循环变量初始化要在 for 之前设置，所有循环条件的判断、循环变量的修改、结束循环控制等都要在循环体内实现。例如：
for(;;) 语句; 等价于 while(1) 语句;
上面求和式的程序可以写成：
s=0; i=1;
for (;;)
{ if(i>100)break;
s + = i;
i ++;
}
（2）省略“表达式”的for语句可以构成不同形式的循环。以下都是求和式程序的等价程序。
① 初始化表达式是逗号表达式，省略第2个和第3个表达式：
for (s = 0, i = 1; ;)
{ if(i>100) break;
s + = i;
i ++;
}
② 省略第1个和第3个表达式：
s=0; i=1;
for (; i <= 100 ;)
{ s+=i;
i ++;
}
③ 把累加计算表达式放在第3个表达式处，构成逗号表达式，循环体为空语句：
for (s = 0, i = 1; i <= 100 ; s + = i, i ++);
读者还可以根据需要和习惯，写出不同形式的for循环结构。
3.应用举例
【例2-18】求n！= 1×2×3×…×n的值，n从键盘输入。
#include <iostream>
using namespace std;
int main()
{ int i,n;
long int t;
cout<<"input one integer n:{n＜=16}";
cin>>n;
t=1; //乘法器初值为1
for(i=1;i<=n;i++) //步长循环求阶乘
t *= i;
cout<<n<<"!= "<<t<< endl;
}
程序运行结果为：
n = 5
5 != 120
【例2-19】输入若干个学生成绩，分别统计出成绩在85～100分，60～84分及60分以下这3个分数段的人数。
学生人数用变量n表示，学生的成绩用变量score表示，统计3个分数段人数的计数变量分别用n1、n2和n3表示，解决这个问题的程序如下：
#include <iostream>
using namespace std;
int main()
{ int i,n,n1,n2,n3;
double score;
cout << "n = ";
cin >> n;
n1=0; n2=0; n3=0;
for(i=1;i<=n;i++) //步长循环计算学生数
{ cin>>score; //输入一个学生成绩
if(score>=85) n1+=1;
else if(score>=60) n2+=1;
else n3+=1;
}
cout << "85--100: "<< n1 << endl;
cout<<"60--84 :"<<n2<<endl;
cout<<" 0--59 :"<<n3<<endl;
}
程序执行结果：
n = 5
65 90 78 100 80
85--100: 2
60--84 :3
0--59 :0
【例2-20】从键盘输入若干个数，求出这些数中的最大值。
用变量n表示输入数据的个数，用变量x表示需输入的数据，并设置一个变量max来存放最大值，求n个数最大值的程序如下：
#include <iostream>
using namespace std;
int main()
{ int i,n;
double x, max;
cout << "n = ";
cin >> n;
cin>>x; //输入第1个数据
max=x; //用第1个数据置累加器初值
for(i=2;i<=n;i++) //步长循环计数
{ cin>>x; //输入数据
if(x>max) max=x; //求当前最大值
}
cout << "max = " << max << endl;
}
在程序设计中，通常累加器置初值为0，乘法器置初值为1。在这个程序中，变量max用于记录数据集中的最大值，被处理的数据对象不能预知范围，因此max的初值置为第一个输入数据。
程序运行结果：
n = 5
75 68 85 91 54
max = 91
【例2-21】求斐波那契数列（Fibonacci）的前n项。斐波那契数列形如：
0，1，1，2，3，5，8，13，21…
其定义规律是：第0项a0 =0，第1项a1=1，后续各项为：
a2=a0+a1, …, ai = ai-1 + ai-2, …, an = an-2 + an-1
从第2项开始，每一项都等于前面两项之和。
在程序中，可以使用3个变量a0、a1和a2进行迭代：开始时，置a0为0，a1为1，根据a0和a1的值计算第2项a2，即a2=a0+a1；然后用a1的值替换a0的值，用a2的值替换a1的值，用a3=a1+a2求得第3项a3的值；如此迭代下去，可以求出斐波那契数列各项的值。按上述算法编写程序如下：
#include <iostream>
using namespace std;
int main()
{ int n,i,a0,a1,a2;
cout<<"n = ";
cin>>n;
a0=0; //对第0项赋初值
a1=1; //对第1项赋初值
cout<<a0<<'\t'<<a1<<'\t';
for(i=3; i<=n; i++)
{ a2=a0+a1; //求新一项的值
cout<<a2<<'\t';
if(i%10==0) cout<<endl; //格式控制，每行显示10项
a0=a1; a1=a2; //迭代
}
}
程序运行结果为：
n = 20
0 1 1 2 3 5 8 13 21 34
55 89 144 233 377 610 987 1597 2584 4181
可以发现，求斐波那契数列的迭代程序并不需要用 3 个变量实现。若 a0 初值为 0，a1 初值为1，则由赋值语句的性质可知，若有：
a0 = a0 + a1;
首先读出 a0的值，与a1的值相加，赋给变量a0，覆盖了原来的值，即得到第3项的值，此时， a0、a1分别存放数列第3项和第2项的值。然后由：
a1 = a1 + a0;
得到数列的第4项值。在循环体内用这两个语句如此迭代，可以同时产生两个数列的当前项。
修改上述程序如下：
#include <iostream>
using namespace std;
int main()
{ int n,i,a0,a1;
cout<<"n = ";
cin>>n;
a0 = 0;
a1 = 1;
cout<<a0<<'\t'<<a1<<'\t';
for(i=2;i<=n/2;i++) //每趟循环求两项
{ a0=a0+a1;
a1 = a1 + a0;
cout << a0 << '\t' << a1 << '\t';
if(i%5==0) cout<<endl;
}
if(n>(i-1)*2) cout<<a0+a1<<endl; //n为奇数，输出最后一项
}
程序运行结果为：
n = 15
0 1 1 2 3 5 8 13 21 34
55 89 144 233 377
2.2.4 循环的嵌套
1.嵌套循环的执行
所谓循环嵌套，就是在一个循环语句的循环体内又包含循环语句。各种循环语句都可以互相嵌套。例如：
while (…)
{ …
while (…)
{…}
…:
}
又如：
for(…)
{ …
for(…)
{…}
…
}
再如：
for (…)
{ …
while (…)
{…}
…
}
以上都是循环的嵌套。循环还可以多层嵌套，称为多重循环。
在嵌套循环结构中，内循环语句是外循环体语句序列的一个语句，外循环每执行一次循环体，内层循环语句都要完成全部循环。例如，外循环的循环次数为 m，内循环的循环次数为 n，如果外循环结束，则内循环体内的语句将被执行m×n次。
【例2-22】测试循环执行次数。
#include <iostream>
using namespace std;
int main()
{ cout<<"i\tj\n";
for(int i=1;i<=3;i++) //外循环
{ cout<<i;
for(int j=1;j<=3;j++) //内循环
{ cout<<'\t'<<j<<endl; }
}
}
程序运行结果：
i j
1 1
2
3
2 1
2
3
3 1
2
3
在内层循环体中，一般不应该修改外层的循环控制变量，以免引起执行的混乱。
2.应用举例
【例2-23】百鸡问题。已知公鸡每只5元，母鸡每只3元，小鸡每3只1元。现要用100元买100只鸡，问公鸡、母鸡和小鸡各为多少？
解决这个问题无法使用代数方法，可以使用“穷举法”来求解。所谓穷举法，就是把问题的解的各种可能组合全部罗列出来，并判断每一种可能的组合是否满足给定条件。若满足给定条件，就是问题的解。
假定用变量x、y和z分别表示公鸡、母鸡和小鸡的数目。当取定x和y之后，z=100-x-y。据题意可知，x的取值为0～19 之间的整数，y的取值为0～33 之间的整数。所以我们可以用外层循环控制x从0到19变化，内层循环控制y从0到33变化，然后在内层循环体中对每一个x和y，求出z，并判别x、y和z是否满足条件：5*x+3*y+z/3.0==100，若满足就输出x，y和z。使用z/3.0是因为每3只小鸡1元，若相除结果不是整数，则说明不符合条件。若用z/3，则C++作整除运算，略去商的小数部分，引起程序判断错误。
按分析，编写程序为：
#include <iostream>
using namespace std;
int main()
{ int x,y,z;
cout<<"cock\t"<<"hen\t"<<"chick\t"<<endl;
for(x=0;x<=19;x++) //公鸡的可能数
for(y=0;y<=33;y++) //母鸡的可能数
{ z=100-x-y;
if((5*x+3*y+z/3.0)==100) //小鸡的可能数
cout<<x<<'\t'<<y<<'\t'<<z<<endl;
}
}
程序运行结果：
cock hen chick
0 25 75
4 18 78
8 11 81
12 4 84
【例2-24】求2～100之间的素数。
所谓素数，就是除1和它本身外没有其他约数的整数。例如，2, 3, 5, 7, 11等都是素数，而4， 6，8，9等都不是素数。
要判别整数m是否为素数，最简单的方法是根据定义进行测试，即用2, 3, 4, …, m-1逐个去除m。若其中没有一个数能整除m，则m为素数；否则，m不是素数。
数学上可以证明：若所有小于等于
的数都不能整除 m，则大于
的数也一定不能整除m。因此，在判别一个数 m 是否为素数时，可以缩小测试范围，只需在 2～
之间检查是否存在m的约数。只要找到一个约数，就说明这个数不是素数，退出测试。
使用上述求素数的方法，编写程序如下：
#include<iostream>
using namespace std;
#include<cmath>
int main()
{ int m,i,k,n=0;
for(m=2;m<=100;m++) //循环，测试每一个m值
{ k=int(sqrt(double(m))); //取测试范围
i=2; //约数
while(m%i&&i<=k) //查找m的约数
i++;
if(i>k) //没有大于1的约数
{ cout<<m<<'\t'; //输出素数
n+=1; //记录素数个数
if(n%5==0) cout<<endl; //每行输出5个数据
}
}
}
程序运行结果：
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