判断n是不是素数,只需被2～根号n之间的整数除?
RT,判断n是不是素数,只需被2～根号n之间的整数除,如果都不能被整除,就是素数?
为什么是根号n?
--------------------------------
人气：484 ℃ 时间：2019-08-18 10:45:44
解答
如果一个数n是合数,则可写为n=p*q*……,项数越多则质因数整体越小.
设p为n的最小质因数,则2=p.
即 n=pq>=p*p>sqrt(n)*sqrt(n)=n,此式矛盾,故假设不成立,即 p
推荐
猜你喜欢
