以下是引用stronghao在2008-10-25 16:28:00的发言:316. DS n是否为质数? 1. n的质数都比n开三次方小 2. n的质数都比n开二次方小 版本二: 已知N>1, N是不是prime number感觉比较纠结的题目是这道 (1)n的任何prime factor都大于n^1/3 (2)n的任何prime factor都大于n^1/2 是不是选B? 我也认为是B,不过也很纠结的算出来的,不知道有没有错 NN出来说明一下这题应该这样推论啊? NN出来说明一下这题应该这样推论啊? NN出来说明一下这题应该这样推论啊? 其实想起来比较容易,但是要写出来的话有点麻烦就是。 我是反证的:在(2)的基础上,假设N不是质数,则至少有一个质因子。 1、若N仅有一个质因子A,则必有N=A^k(K为大于1整数)。当k=2,A=N^1/2 ;K>2,A<N^1/2。 2、若N有两个或以上质因子,A、B是其质因子,则A*B是N的因子且<=N。若A*B=N,则其中一个必然一个小于N^1/2 ,一个大于N^1/2,因为A<>B。若A*B<N,则A、B至少有一个小于N^1/2。 由1、2推出假设不成立。因此(2)能推出N为质数。 (1)其实用上面的思路也就证出来了,但写的话比较麻烦。举个反例更简单。比如3和4,都满足(1)
|