Question

C程序设计（第四版）谭浩强著中的例题2.5。有点儿不懂，帮忙给点意见谢谢

例题：给出一个大于或等于3的正整数，判断它是否是一个素数。
给出的算法是：
S1：输入n的值
S2：i=2(i作为除数)
S3：n被i除，得余数r
S4：如果r=0,表示n能被i整除，则输出n“不是素数”，算法结束；否则执行S5
S5：i=i+1
S6:如果i<=n-1,返回S3；否则输出n的值以及“是素数”，然后结束
到这里我都看懂了
之后书上又说：实际上，n不必被2~n-1的整数除，只需被2~n/2间证书除即可，甚至只须被2~n之间的整数除即可。例如，判断13是否为素数，只需将13被2,3除即可，如都除不尽，n必为素数。S6步骤可改为：
S6：如果i<=n，返回S3；否则算法结束。
这里就有点不懂了，当i=n时，还返回S3虚幻也就是说 相当于n/n=1，余数为0，n就不管是什么都会被判定为不是素数。还是说我理解错了？
还有就是只判断13被2,3除即可这个2,3是怎么得出来的。我指的是计算机怎么得出来而不是我们人脑，假如数再大点儿比如47那怎么判断被谁谁除即可？
本人语言初学者，望各位大大给点意见，哪怕给个思路O(∩_∩)O谢谢

Answer 1

这个是算法问题; 举个例子6,
1x6=6, 2x3=6, 3x2=6, 4x?=6, 5x?=6, 6x1=6
乘数从1一直增到6, 同时被乘数会从6一直减到1,那么2x3和3x2就只是乘数与被乘数换位置了,这种情况下就不需要重复计算了.临界值就是6的平方根了.
所以,应该是
S6: 如果i<=n的平方根,返回S3;否则算法结束

追问

也就是说6的根号2.45左右退位取整为2，只判断2；13的根号3.61退位取整为3，只判断2，3。也就是说书上最后的提示是错误的呗，应该加上平方根仨字儿。是这个意思吧

追答

对

Answer 2

其实判断到根号n就好了所以13，只要判断2，3