判断n是不是素数,只需被2～根号n之间的整数除?RT,判断n是不是素数,只需被2～根号n之间的整数除,如果都不能被整除,就是素数?为什么是根号n?--------------------------------
问题描述：
判断n是不是素数,只需被2～根号n之间的整数除?
RT,判断n是不是素数,只需被2～根号n之间的整数除,如果都不能被整除,就是素数?
为什么是根号n?
--------------------------------
答
如果一个数n是合数,则可写为n=p*q*……,项数越多则质因数整体越小.
设p为n的最小质因数,则2=p.
即 n=pq>=p*p>sqrt(n)*sqrt(n)=n,此式矛盾,故假设不成立,即 p