判断质数--单重循环.pptVIP

判 断 质 数 练 习 题 * * 　输入正整数N，判断其是否为质数。 　是则输出“Yes”，否则输出“No”。 问 题 初步想法 根据质数的定义，质数N只有1和N两个因子。 因此，可以从2开始循环到N-1，用N逐个去除这些数，如果在[2, N-1]的范围内找不到第3个因子，则N就是质数。 (以下程序请在VB中运行)(val函数的作用是将字符转化为数字) Input N For i = 2 To N - 1 if N Mod i 0 Then Print Yes else Print No end if Next i 初步想法 上机验证 程序会有多个输出，不符合题目的意思。 原因在于，把输出语句写在了循环内部，造成多个输出。因此，我们需要把输出语句移到循环结束后。 但是，如何才能把循环里面判断的结果带出循环？ 方法一：设一个变量，通常是布尔型，作为标记，循环结束后，根据这个标记输出结果。 (本课堂重点讲述) 方法二：设一个整数变量，在[2, N-1]内每找到一个因子就　　　　加1，循环结束后，如果这个变量大于0，显然就　　　　不是质数。(自己实现) 完整的正确程序 (VB版) N = Val(InputBox(请输入一个整数(其实是字符))) Prim = True For i = 2 To N - 1 if N Mod i = 0 Then Prim = False end if Next i if Prim = True Then Print Yes else Print No end if 程序意思：先假设N是质数，标记为True，然后寻找第3个因子，　　　　　如果找到就改变假设为False，如果找不到则假设不变。　　　　　循环结束后，根据这个标记输出相应结果。 易错点 if … then 后面加else N = Val(InputBox(请输入一个整数(其实是字符))) Prim = True For i = 2 To N - 1 if N Mod i = 0 Then Prim = False else Prim = True end if Next i if Prim = True Then Print Yes else Print No end if 上机验证：当N=13(质数)时正确，但是当N=16(合数)时错误。 试图修改：把True和False换个位置？ 逻辑上显然错了 当输入N = 16时 先假设为True i=2，N mod i=0， Prim赋值为False 逻辑正确 i=3，N mod i0， Prim赋值为True 逻辑错误 i=4，N mod i=0， Prim赋值为False 逻辑正确 …… i=15，N mod i0，Prim赋值为True 逻辑错误 最后一个i最关键 正确的做法 (第5页的程序) 质数的因子比合数的少，因此应该先假设为因子少的情况(True)，然后找更多的因子，找到后改变标记(False)。 循环前已经假设过的情况(True)不要重复赋值 程序优化 减少循环的次数 优化一 正整数N的因子都是成对出现的，以sqr(N)为分界线，两边一一对应，因此只要循环到sqr(N)即可。 优化二 如果正整数N的因子有多个，例如N=16，除了1和16，还有2、4、8都是它的因子，但是循环时发现16 mod 2=0，这时候就已经可以断定16为False，后面的都不用判断了，可以强行退出循环。 程序后的程序 尽量减少循环次数 N = Val(InputBox(请输入一个整数(其实是字符))) prim = True For i = 2 To Sqr(N) if N Mod i = 0 Then prim = False Exit For 循环还没结束，强行退出。 End If Next i If prim = True Then Print Yes Else Print No End If 完整的正确程序 (Free Basic版) Input N Prim = 1 For i = 2 to SQR(N) if N Mod i = 0 Then Prim = 0