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