ghost79

导航

<2009年4月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

统计

留言簿(0)

随笔分类

随笔档案

文章档案

搜索

最新评论

阅读排行榜

评论排行榜

用筛法求2-n之间的所有素数

[问题描述]

用筛法求2-100之间所有的素数可以这样做，将2的倍数但不包括2都划掉，再将3的倍数但不包括3全部划掉，然后是5的，7的但不包括5、7全部划掉，最后剩下的就都是素数。

[输入]

只有一行，即整数n

[输出]

2-n的所有素数

[示例]

输入：
11
输出：
2 3 5 7 11

[问题解答]

#include <iostream>
#include <math.h>

using namespace std;

int main( void )
{
    int n;
    cin >> n;
    int *p = new int[ n + 1 ];
    for( int i = 2; i <= n; i++ ) p[ i ] = i;

    int z = 2, i;
    while( z * z <=  n ) {
        i = z * 2;
        while( i <= n ) {
            p[ i ] = 0;
            i = i + z;
        }

        do z++; while( !p[ z ] );
    }

    for( int i = 2; i <= n; i++ )
        if( p[ i ] ) cout << i << " ";

    delete []p;
    
    system( "PAUSE" );
    return 0;
}

posted on 2009-04-09 13:16 C家家 阅读(161) 评论(0)  编辑 收藏

评论

标题  
姓名  
主页
内容   
请输入验证码:
*
  登录  使用高级评论  Top 订阅回复  取消订阅
[使用Ctrl+Enter键可以直接提交]