用筛选法求100之内的素数(C语言 数组) |
您所在的位置:网站首页 › c语言数组求和求平均原理是什么样的 › 用筛选法求100之内的素数(C语言 数组) |
1.解释下什么是筛选法? 筛选法又称筛法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。 2.程序步骤: 先将1挖掉(因为1不是素数)。 用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。 用3去除它后面的各数,把3的倍数挖掉。 分别用5…各数作为除数去除这些数以后的各数。3.具体应用(求100以内的素数): 基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列,把不是素数的数全部赋值为0,最后只输出不是零的数即素数。1不是素数,首先把它换为0。剩下的数中选择最小的数是素数,然后把它的倍数全部换为0。依次类推,直到结束。 如有: 1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 301不是素数,换为0。剩下的数中2最小,是素数,然后把它的倍数全部换为0,余下的数是:0 2 3 0 5 0 7 0 9 011 0 13 0 15 0 17 0 19 021 0 23 0 25 0 27 0 29 0剩下的数中3最小,是素数,然后把它的倍数全部换为0,如此下去直到所有的数都被筛完,求出的素数为:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 4.代码如下(vc6.0): //用筛选法求100以内的素数 #include #include int main() { int i,j,k=0,a[100]; for(i=0;i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |