试除法

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

试除法

试除法是整数分解演算法中最简单和最容易理解的演算法。首次出现于义大利数学家费波那契出版于1202年的著作。给定一个待分解的正整数"n"，试除法是用小于等于formula_1的每个素数去试除。如果找到一个数能够整除除尽，这个数就是可分解整数的因数。若"n"为合数，则试除法一定能够找到"n"的质因数，因为"n"最小的质因数不大于其平方根，所以如果这个演算法“失败”，也就证明了"n"是个素数。某种意义上说，试除法是个效率非常低的演算法，如果从2开始，一直算到formula_1需要 formula_3次试除，这里formula_4是小于x的素数的个数。这是不包括素性测试的。如果稍做变通——还是不包括素性测试——用小于formula_1的奇数去简单的试除，则需要formula_6次。这意味着，如果"n"有大小接近的素因数（例如公钥密码学中用到的），试除法是不太可能实行的。但是，当"n"有至少一个小因数，试除法可以很快找到这个小因数。值得注意的是，对于随机的"n"，2是其因数的概率是50％，3是33％，等等，88％的正整数有小于100的因数，91％的正整数有小于1000的因数。

将军澳隧道

下施蒂利亚

三才图会

快门

笑岩德宝

汉质帝

蔡濯堂

词人

上施蒂利亚

阿纳尔瑞

松桃苗族自治县

施泰尔马克州