jj56题看不懂呀

dream2ture

56.  1 (DS) p is prime?
              A. the only positive factor greater than sqrt(p) is p.
              B. the only positive factor less than sqrt(p) is 1.

解：对任意一个p，设p=a*b，不妨令a<=b

如果p是一个质数，那么a=1,b=p

如果p是一个合数，那么a>1

 

i àif p=4 sqrt(p)=2, the only positive factor greater than 2 is 4. But 4 is not prime but a composite

ii àagain if p=4

 

Note: This is an interesting topics in Number theory : prime number test.就是说给定一个数p，问p是不是素数。最简单判定方法是：

如果p是2，那么直接确定素数；

如果p是个偶数，显然也不是素数；

如果是奇数，那么，拿p依次除以所有小于p的数，如果有一个整除，那么这个数就不是prime；如果没有一个整除，那么p就是prime的。

但是其实并没有必要除所有小于p的数。因为p是奇数，除偶数是肯定不整除的，只需要除那些小于p的奇数就可以了。

其实还有更加简单的方法，如果p=a*b（a<=b)，那么可以肯定a<=sqrt(p)，也就是说，如果p是一个合数，那么它的一个因子必然小于p的平方根（不然的话，这些因子的乘积会大于p了）.有了这么个发现，我们就不必要依次去除小于p的奇数，仅仅依次除以小于p的平方根的奇数就可以了。

如果条件说，小于等于sqrt(p)的所有自然数里面，只有1是p的因子，就说明，这些小于等于sqrt(p)且大于1的自然数 ，都不能整除p，所以p是素数。（题目里面只说了小于sqrt(p)就忽略掉了完全平方数的Case）

（但愿说明白了）