1.1.4 算法的描述

在算法设计过程中，算法的描述方式主要有4种：自然语言、流程图、伪代码和程序设计语言，如表1.1所示。

下面以判断一个大于2的正整数是否为素数的问题为例，分别采用上述四种方式进行描述。

解题思路：素数是指只能被1和自身整除的数。在判断一个数是否是素数的时候，通常采用的是这样的方式：假设现在这个数是7，就从2开始，用2去除7，如果余数不为零，就接着用3去除7，……，直到用6去除7为止，此时余数依然不为零，因此得出结论——7是素数。对于数字n来说，其需要尝试的数的范围就是2~n-1，其实算法还可以进行优化，不需要测试到n-1，只需要测试到即可，原因在于就是分界线。如果在[2,]区间里有一个数h能够整除n的话，在[, n-1]区间里必定会有一个数k与之对应，有h×k=n。例如15这个数，我们在[2,]区间里找到一个数3能够整除它，在[, 14]区间里就有一个数5与之对应，有3×5=15。对应地，如果在[2,]区间里找不到能够整除n的数，那么在[, n-1]区间里也肯定没有能整除它的数。

1.自然语言

用日常生活中使用的语言来描述算法，相对来说易于理解，但书写起来比较烦琐，也有可能因为表述不到位引起歧义，对于较为复杂的问题较难表述准确。对于计算机来说，自然语言是不可识别和执行的。

判断一个大于2的正整数是否为素数的算法描述如下。

步骤1：输入n。

步骤2：定义变量i，赋初始值为2。

步骤3：判断n除以i的余数是否为0，如果为0，则转到步骤6。

步骤4：变量i的值自加1。

步骤5：判断i的值是否小于，如果小于，则返回步骤3。

步骤6：判断i的值是否大于，如果大于，则输出“This is not a prime.”；否则，输出“This is a prime.”。

2.流程图

流程图使用不同的图框来表示各类操作，在图框内部写出步骤，再用箭头连接起来表示先后顺序。通过图形的方式来描述算法，直观而又形象。判断一个大于2的正整数是否为素数的算法流程如图1.3所示。

3.伪代码

伪代码是一种介于自然语言与计算机语言之间的用来描述算法的语言，参照计算机语言的书写形式来表示算法的各个步骤，相比计算机语言更加接近自然语言，相对来说容易理解。伪代码旨在用接近自然语言的形式描述程序的执行过程，一般是不能被计算机直接执行的。判断一个大于2的正整数是否为素数的算法的伪代码描述如下。

步骤1：输入n。

步骤2：i=2。

步骤3：循环直到i大于。

3.1如果n%i==0，break。

3.2i=i+1。

步骤4：如果i大于，输出“This is not a prime.”，否则输出“This is a prime.”。

4.程序设计语言

也可以直接用计算机语言的形式来描述算法，通常是将算法写成子函数。这样的算法是可以直接在计算机上执行的。判断一个大于2的正整数是否为素数的算法的程序设计语言描述如下。

---

int main()
   { 
      int i, n; 
      scanf("%d", &n); 
      for(i=2; i < sqrt(n); i++)
       { 
         if(n%i==0)
              break; 
        } 
       if(i >sqrt(n)) 
          printf("This is a prime."); 
       else 
          printf("This is not a prime."); 
       return 0; 
      }     

---