Question

Pascal的一道完善程序（很基础的题）

判断质数
题目描述:
给出一个正整数，判断这个数是否是质数。
输入:
一个正整数n(1 ≤ n ≤ 10000)。
输出:
如果n是质数，输出”YES”；否则，输出”NO”。
输入样例:
10
输出样例:
NO
程序：
Var
①: Integer;
Begin
Read(n);
If n = 2 Then WriteLn( ② )
Else If ( ③ ) Or (n Mod 2 = 0) Then WriteLn('no')
Else Begin
i := 3;
While i * i <= n Do Begin
If ④ Then Begin
WriteLn('no'); exit;
End;
i := i + 2;
End;
WriteLn('yes');
End;
End.

“While i * i <= n Do Begin
If ④ Then Begin
WriteLn('no'); exit;”为什么只要计算到<=根号n的数就可以了？我们老师上课的时候好像说了一个定义，我忘了。。哪位大虾能说一下？谢谢了！

Answer 1

LZ的意思是不用填空了吧...
我就说说最后一个问题：什么只要计算到<=根号n...
请LZ好好想想，一个数N，分解质因数，假设分解成
N=p1*p2*p3*...*pn {pn>=2}
{程序也正是从2（最小的质数）开始算的}
如果循环到px满足 N=px*px {也就是循环到根号了}且之前没有N的因数，我们才有继续循环下去的意义。
如果在px后有一个py 满足 N mod py=0,那么一定会有某个pz<=px 使 py*pz=N
这时候只能有两种情况：
1. 2<=pz<=px<=py<n 这样的话在循环到py时就已经有一个因数了，与前提相悖。
2. pz=1,py=N 这样就是质数了，还有继续循环的意义吗?
所以，在trunc(sqrt（N）)之前如果有质因数，N就是合数，若没有，就是质数。（不过注意，1,2,3需要特判，因为1不是质数也不是合数，2,3的开平方取整是1，就不能从2开始循环了，题中用的算法效率较低，理解一下就行了...）

Answer 2

对于一个正整数n （n>1 且n是质数不谈) 如果它是完全平方数 那么trunc(sqrt(n))就是这个数最大的约数 这个理解吧
那么如果这个数n不是一个完全平方数 那么trunc(sqrt(n))就是他的有理数约数中的最大范围 是不可能被超过的
那么在这道题中 只要运算到trunc(sqrt(n))就可以节省很多没必要的重复运算 增加
效率 对程序运行时很有帮助的吧 呵呵！！
1:这个就不用写了吧 呵呵 直接抄变量就可以了
2：‘yes’
3：
4： (n mod i=0)

Answer 3

①：n,i
②：'Yes'
③：n=1
④：n mod i = 0