频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
欧拉筛法求素数(代码实现)
2017-12-05 13:39:06         来源:Mercury  
收藏   我要投稿

代码

#include 
#include 

bool flag[10001] = {0};
int p[10001] = {0};

int main()
{
    int i, n, cnt = 0, j;
    scanf("%d", &n);

    for (i = 2; i <= n; ++i){
        if (flag[i] == 0)
            p[cnt++] = i;
        for (j = 0; j < cnt && i * p[j] <= n; ++j){
            flag[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }

    for (i = 0; i < cnt; ++i)
        i == cnt - 1 ? printf("%d\n", p[i]) : printf("%d ", p[i]);
    return 0;
}

说明


flag标记下标是否为合数 p按顺序存放素数 flag[i * p[j]] = 1筛掉i这一素数的素数倍数。 若i能整除p[j]则跳出循环,等到p[j]==i时再筛去i*p[j]这个数。即仅在合数的最大因子作为乘数时筛去这一合数。 时间复杂度O(n)

点击复制链接 与好友分享!回本站首页
上一篇:JAVA对象序列化操作讲解
下一篇:Spring OXM-XStream设置使用别名
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站