如何判断一个较大的数是合数(如何快速判断一个较大正整数是质数还是合数)

如何快速判断一个较大正整数是质数还是合数?

如何判断一个较大的数是合数(如何快速判断一个较大正整数是质数还是合数)(1)

如果是判断一个100以内或比较小的正整数是不是质数,我们只需要运用比较熟悉的2,3,5,7,11,13这些质数去除这个数,如果都不能整除,则该数就是质数,如果能够被其中某个质数整除,则这个数就是合数。但对于一个较大的整数判断它是合数还是质数,如何快速作出判断呢?或者说从最小的质数2开始,要判断到那个质数终止呢?

比如,899是合数还是质数?

如何判断一个较大的数是合数(如何快速判断一个较大正整数是质数还是合数)(2)

我们从2开始经过验算已经确认它不能被2,3,3,7,11,13,17,19整除了,至此是否就可以下结论它是质数呢?显然是不行的,再继续验算下去,它能被29整除,即899÷29=31,所以899是合数。

显然,判断一个数是不是质数,依次从最小的质数2开始依次验算它否被这些质数整除,但问题是如果前面连续验算了许多个仍然没有出现过整除,究竟要验算到那个质数为止呢?是不是要验算到这个数本身才能得出为质数的结论?否则要验算到能否被多大的质数整除才能作出判断是质数呢?

下面先了解一下质数的一些特征:

假设所判断的整数为N,

当N<2×3时,如果N不是2的倍数,则N是质数;

当N<3×5时,如果N不是2或3的倍数,则N是质数;

当N<5×7时,如果N不是2或3或5的倍数,则N是质数;

当N<7×11时,如果N不是2或3或5或7的倍数,则N是质数;

当N<11×13时,如果N不是2或3或5或7或11的倍数,则N是质数;

一般地,当N<a×b(a,b为连续质数,且a<b)时,如果N不是2或3或5,…或a这些连续质数的倍数,则N是质数;

因此,判断一个较大的整数N是不是质数,其做法是:找到两个连续的质数a,b(a<b),使得N最接近于ab,且N<ab,然后一一验证N是否能被所有小于a的质数整除即可。

显然,对于较大的整数N,要找到两个连续的质数a、b,使得N<ab还是有点困难和麻烦的。注意到a<b,而a、b是连续的质数,所以 a^2<N<ab,即a<√N<√ab,

所以可用[√N]([√N]表示不超过√N的最大整数)替代a。

例如,判断2011是质数还是合数?

因为[√2011]=44,所以要判断2011是不是质数,只需要验证2011能否被小于44的某个质数整除就可以了,完全没必要验证到2011.

也就是说,最多只需要判断2011能否被43,41,37,31,29,23,19,17,13,11,7,5,3,2这些数中的某一个整除即可。

由于2011都不能被这些质数整除,所以2011是质数。

如何判断一个较大的数是合数(如何快速判断一个较大正整数是质数还是合数)(3)

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页