素数

  一个大于1的自然数,如果只有1和它自身作为因子,这样的数就是素数.

  19781030日下午9时,上述的数被发现,它成为那时最大的已知素数.这个素数可写为221701-1,它是L·尼克尔和C·诺尔(两人均系中学生)在计算机上运作了1800小时后发现的.接着C·诺尔又独自发现了一个更大的素数223209119795月利物浦实验室的H·尼尔森发现了一个比诺尔大得多的素数2444971

 

  虽然今天的计算机已经有了探寻素数的程序,但古希腊数学家埃拉托斯散(Eratosthenes,公元前275—公元前194)却早已发明了求比某给定数小的素数的筛法技巧.下图圆圈内的数是小于100的素数.

 

  

  程序:

  1)划掉1,因为它不归于素数类.

  2)圈起2,这是最小的正的偶素数.现在划掉所有2的倍数.

  3)圈起3,即下一个素数.现在划掉所有3的倍数.可能其中有些已作为2的倍数被划掉.

  4)圈起下一个未被划掉的数,即5.现在划掉所有5的倍数.

  5)继续上述过程,直至100之内的所有数要么被圈起,要么被划掉.