Question

下面是判断n是否是一个质数的程序，运算次数比较多，结构也比较复杂，例50中，d≤n－1，按质数的定义，即可，这是什么原因？你觉得这改法好不好？有没有更好的办法，其他步骤有没有更改的地方，不妨给出你的程序？

10

INPUT“n=”；n

20

flag=1

30

IF　n＞2　THEN

40

　　d=2

50

　　WHILE　d＜=n－1　AND　flag=1

60

　　　IF　n MOD　d=0　THEN

70

　　　　Flag=0

80

　　　ELSE

90

　　　　d=d＋1

100

　　　　END　IF

110

　　　WEND

120

ELSE

130

　IF　flag=1　THEN

140

　　　PRINT n；“是质数．”

150

　ELSE

160

　　PRINT n；“不是质数．”

170

　END　IF

180

END　IF

190

END

Answer 1

答案：略
解析：

如11是质数，没有必要用2，3，…，10分别去除，只要不能被(也可表示为int(sqvt(11))整除即可．因为，若为整数，显然x不是质数，若不是整数，取其整数部分，不会有超过的约数了． 　　将50中d＜=n－1，改为，减少了循环次数，但每次程序运行都计算判断无意中增加了运算量．应在20与10间加入参数，再将d＜=n－1，改为d＜=a． 　　需改进的地方还有，偶数(除2外)显然不是质数，因此将90中步长d=d＋1改为d=d＋2 程序略