如何证明埃拉托斯特尼筛法!检查一个正整数N是否为素数,最简单的方法就是试除法,将... 埃拉托斯特尼筛法故事

什么是筛法？（数论中古老的方法） 在数论中有广泛应用的一个初等方法，起源于古老的埃拉托斯特尼筛法。所谓筛法，可描述如下：①给定“被筛集合”。这是依赖于某一参数□的集合族□(□)，□。每一集合□(□)由有限个（可重复的）整数组成，且当□→时元素个数也趋于无穷。②给定“筛”。这是由无限多个不同的素数组成的集合□以及对每一□给定□(□)个模□的不同的剩余类□(□)所组成，其中1≤□(□)<；□。③进行“筛选”。给定正数□>；2，把集合□(□)中属于剩余类□(□)的所有元素都去掉，其中□≤□，□。剩下的元素所组成的□(□)的子集及其元素个数，均记为□(□(□)，□(□)，□，□)，是□和□的函数，称之为筛函数。当□(□)仅有一个剩余类□≡0(mod□)时，筛函数记为□(□(□)，□，□)。选取不同的被筛集合、筛和□，经筛选后，可得到具有不同算术性质的子集，所以许多数论问题有可能用筛法来研究。例如，取参数□为正整数□，□(□)由某些大于1不超过□的整数组成，□是全体素数。再取□=□（整数□≥2）。于是□(□(□)，□，□)是由□(□)中所有大于□不超过□，且其素因子都大于□的整数组成。这种整数是不超过□-1个素因数的乘积。当□=2时即是埃拉托斯特尼筛法。又如，设□、□是正整数。以｛□，。什么叫“筛法” “筛法”是一种求质数的方法。是公元前。由古希腊著名数学家埃拉托色尼提出的，所以，也叫埃拉托色尼筛法。筛法的简述 具体做法是：给出要筛数值的范围 n，找出 n以内的素数p1，p2，p3，.，pk。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去.因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛法”，简称“筛法”。向左转|向右转什么是埃拉托斯特尼筛法？

#筛法求素数#素数