首页 > 代码库 > Eratosthenes筛选法计算质数
Eratosthenes筛选法计算质数
《C和指针》第6章第4道编程题：
质数就是只能被1和本身整除的数。Eratosthenes筛选法是一种计算质数的有效方法。这个算法的第一步就是写下所有从2至某个上限之间的所有整数。在算法的剩余部分，遍历整个列表并剔除所有不是质数的整数。
后面的步骤是这样的。找到列表中的第1个不被剔除的数（也就是2），然后将列表后面所有逢双的数都剔除，因为它们都可以被2整除，因此不是质数。接着，再回到列表的头部重新开始，此时列表中第一个尚未被剔除的第1个数是3，所以在3之后把每逢第3个数（3的倍数）剔除。完成这一步之后，再回到列表开头，3后面的下一个数是4，但它是2的倍数，已经剔除，所以将其跳过，轮到5，将所有5的倍数剔除，这样依次类推、反复进行，最后列表中未被剔除的数均为质数。
编写一个程序，实现这个算法，使用数组表示列表。每个数组元素的值用于标记对应的数是否已被剔除。开始时数组所有元素的值都设置为TRUE，当算法要求“剔除”其对应的数时，就把这个元素设置为FALSE。如果你的程序运行于16位的机器上，小心考虑是不是把某个变量声明为long。一开始先使用包含1000个元素的数组。如果你使用字符数组，使用相同的空间，你将会比使用整数数组找到更多的质数。你可以使用下标来表示指向数组首元素和尾元素的指针，但你应该使用指针来访问数组元素。
除了2之外，所有的偶数都不是质数。数组中的元素只对应奇数可以使程序的空间效率大为提高。
1 /* 2 ** 用Eratosthenes筛选法输出质数 3 */ 4 #include <stdio.h> 5 6 void Eratosthenes( char *mark, int len ); 7 8 int 9 main()10 {11 char mark[2000];12 int i;13 14 /*15 ** 将数组所有元素设置成‘1‘16 */17 for( i = 0; i < 2000; ++i )18 *( mark + i ) = ‘1‘;19 20 Eratosthenes( mark, 2000 );21 22 /*23 ** 下标0对应的质数是2，直接输出24 */25 printf( "%d ", 2 );26 int c = 1; // c用来计算输出个数，控制每输出10个换行 27 28 for( i = 1; i < 2000; ++ i )29 {30 if( *( mark + i ) == ‘1‘ )31 {32 printf( "%d ", 2 * i + 1 ); // 数组中的元素只对应奇数，所以下标i对应2*i+133 c ++;34 if( c % 10 == 0 )35 printf( "\n" );36 else37 printf( " " );38 } 39 }40 41 return 0;42 }43 44 /*45 ** Eratosthenes函数，筛选质数46 */47 void 48 Eratosthenes( char *mark, int len )49 { 50 int i, j;51 for( i = 1; i < len; ++ i )52 {53 if( *( mark + i) == ‘1‘ )54 {55 for( j = i + 1; j < len; ++ j )56 {57 // 把2*i+1的倍数剔除，即设置为‘0‘58 if( ( 2 * j + 1 ) % ( 2 * i + 1) == 0 )59 *( mark + j ) = ‘0‘;60 }61 }62 }63 }
Eratosthenes筛选法计算质数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。