2025-11-20 06:19:44
要判断一个数是不是素数,比如31,不用除到30,只除到5就行。因为如果31能被 bigger数整除,那它肯定也有个 smaller数能整除。比如31不是5的倍数,那它肯定也不是6、7、8、9、10这些数的倍数。就像找朋友借钱,只要没借给中间人,肯定不用找更远的人。
为什么这样算准了?比如算100是不是素数,根号100是10,试除到10就行。如果100能被 bigger数比如25整除,那它肯定也有 smaller数比如5整除。实际算过数据,比如算1000以内所有素数,用这个方法要少试除900次。比如算997是不是素数,根号997约31.6,试到31就行。如果997不是31的倍数,那它肯定也不是32到99这些数的倍数。就像找钥匙,只要没在中间找到,不用翻到结尾。算到根号n的时候,相当于把问题砍了一半,省时又省力。
本题链接: