写出判断整数n(n>2）是否为质数的算法.第一步：给定大于2的整数n；第二步：令i=2;第三步：用i除n,得到余数r;第四步：判断r=0是否成立,若是,则n不为质数,结束算法；否则,将i的值增加1,仍用i

Question

写出判断整数n(n >2）是否为质数的算法.第一步：给定大于2的整数n；第二步：令i=2;第三步：用i除n,得到余数r;第四步：判断r=0是否成立,若是,则n不为质数,结束算法；否则,将i的值增加1,仍用i表示；第五步：判断i >(n-1)是否成立.若是,则n是质数,结束算法,否则,返回第三步.疑问：我不明白的就是第五步,为什么当
i >(n-1)时,n就是质数?还有,第五步中的i指的是2还是2增加1以后的值?

Answer 1

质数的概念是,除了一与其本身,再不能被其他整数整除的数.所以i>(n-1)就表示被除数等于除数,也就是i=n,那么n除了一和自身就没有其他可以整除他的数了,所以n为质数
比如3,3÷2余1进行第五步,i=3,3÷3=1余0再判断i是否大于(n-1),i=3>(3-1)成立,所以3是质数