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 程序略