怎样快速地分辨出一个自然数,是质数还是合数?
没有绝对的快速——
但是有一些建议方法。对于某一个数来说,主要是靠试。具体地说,用从2到根号n的质数依次尝试,看是否是该数的因数,如果都不是,说明该数是质数。由于只需要尝试不到根号n个因子,运算就小多了。比如,1357这个数是否为质数呢?只要将1到36之间的质数去尝试即可,实际上只有2,3,5,7,11,13,17,19,23,29,31。(因为大多数中学生对于100以内的质数还是比较熟悉的)
顺便说一下,上述方法也可以用来在一定范围内寻找质数。即,将每个质数的整倍数划掉,每个质数划一轮,将从2到根号n的各质数都轮过来之后,剩下未划掉的数字就是质数。