长河网

投稿
  1. 首页首页
  2. 文化

找出n如何找出n(比如100)以内的全部素数

长河网 • 2019-01-22 23:15:34 • 文化 • 阅读 21
数学教学研究本公众号内容均由邵勇本人独创，可以转发，但转载则需获得邵勇本人的授权。每周推送两到三篇内容上有份量的数学文章，但在行文上力争做到深入浅出。几分钟便可读完，轻松学数学。 本期所讲内容是有关素数的，属于数论的范畴，但不用担心，我力
原标题：如何找出n(比如100)以内的全部素数数学教学研究本公众号内容均由邵勇本人独创，可以转发，但转载则需获得邵勇本人的授权。每周推送两到三篇内容上有份量的数学文章，但在行文上力争做到深入浅出。几分钟便可读完，轻松学数学。本期所讲内容是有关素数的，属于数论的范畴，但不用担心，我力争讲得深入浅出，相信您仔细阅读，一定可以理解。今天是周末，若没有时间细读，可以先收藏起来，待以后有时间再读。如何找出任意一个正整数n以内的全部素数？比如说，n等于100，300，1000，34567，......。我们知道有一个所谓的“埃拉托色尼筛法”，它可以逐步”筛“出越来越多的素数。它的做法是：把从1到n的所有正整数从小到大按顺序排列，可以排成一行或一列，也可以排成矩阵的形式，比如n=157，我们就把第一行排1,2,3,4,5,6,7,8,9,10这十个数；第二行排11,12,...,20这十个数，......，到第15行就排满了前150个数，再在第16行排151到157这七个数。下面我们以n=100为例，看一看如何用“埃拉托色尼筛法”，以最节省的方式，找出100以内的全部素数。“埃拉托色尼筛法”的具体操作步骤是：第一步：删除第一个数1。第二步：把目前没有被删除的数中第一个数（最小的数）画圈，然后把这个画圈的数后面所有这个数的倍数删除（注意，这里的删除一般是在上面画个斜线），其实，这第二步画圈的数就是2，被删除的数就是4，6，8，......。第三步：与第二步的操作方式类似，具体来说就是把目前没有画圈也没有被删除的数中的最小的一个数即3画圈，再把比3大的3的倍数删除，即删除，9，15，......（注意，3的倍数中有的也是2的倍数，比如6,12等等，之前已经被删除过了；当然在6,12等等上面再画个斜线也未尝不可，这不影响我们的操作程序）。这样一直做下去，一定可以把所有100以内的素数全部找出来。那么，这样做大概需要多少步呢？按说应该是有多少个素就要进行多少步。现在我们还不知道小于100的素数有多少个，比如说有32个，那么，32步下来，任务也够繁重的。那么，是不是非要进行这么多步不可呢？回答是，不必。我们完全不必进行这么多步，我们要做的步数可以少很多。具体来说，把100开平方：√100（即根号100，注意，下文中都这样表示）。我们取100的平方根的整数部分，即10（正好是10，但一般情况下不一定正好是整数，那就取它的整数部分，比如若n=101，则101的开平方是10点几，我们取它的整数部分10）。所以，我们的结论是，只需把“画圈、删除”这一重复性操作进行到所有不大于10的正整数都被画圈或删除。具体来说，不大于√100的最大素数是7，所以，“画圈、删除”操作进行到把7画圈并把7之后7的倍数删除掉这一步即可。不大于10的的素数有2，3，5，7，共4个，也就是说，我们只需做4次上面所说的“画圈、删除”操作即可。这样做下来，所有画圈和没有被删的数的全体就是小于100的全部素数。如下图所示。数下来，100以内一共有25个素数。您可能要问，画圈的是素数是没有问题的，被删除的数不是素数也是没有问题的，但4次“画圈、删除”操作之后，还有很多既没有画圈也没有被删除的数，它们一定是素数吗？回答是：它们一定是素数！为什么呢？我下面来讲解，请慢慢读，仔细读。用反证法。因为在上述四步操作之后，在√100（即10）以内已经没有未画圈和未被删的数了，所有未画圈和未被删除的数都位于√100和100之间。所以，我们假设在√100和100之间这些未画圈和未被删除的数中有某个数是合数（不是素数即为合数）。设这个数为p，那么√100

本文来自投稿，不代表长河网立场,转载请注明出处： http://www.changhe99.com/a/Gywy477Prj.html

找出n n个数中找出前k大个数 找出从1~n最大值 找出与众不同的一个n 找出n个数中第k大的数 n个数找出最大的k个 输入n个数 要求找出n个数的最 找出近义
赞 (0)
长河网 找出n如何找出n(比如100)以内的全部素数

可能喜欢

相关推荐