| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 463 人关注过本帖
标题:大型数组筛法
只看楼主 加入收藏
pavilion4994
Rank: 1
等 级:新手上路
帖 子:29
专家分:0
注 册:2013-10-17
结帖率:100%
收藏
 问题点数:0 回复次数:4 
大型数组筛法
想用筛法选10^8内素数,但定义10^8元素的数组用常规求小数组的筛法无法成功运行,请教如何用定义大型数组用筛法
搜索更多相关主题的帖子: 如何 元素 
2013-12-12 23:40
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
其中2的倍数就不要存了,数量一下子就少了一半
因为状态只有“是 和 否”,1bit就够了,那么只需要 10^8/2/8 个字节,不足 6M Bytes
2013-12-13 08:38
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
根据上面的思路写的纯C代码,在gcc4.8.1(编译参数-std=c99)上编译测试通过
因为我上面说过“其中2的倍数就不要存了”,所以代码复杂了一点,如果你存2的倍数的话,代码会更简单一些,自己改
程序代码:
#include <stdio.h>
#include <stdlib.h>

#define N 100000000u

int main()
{
    #define UINT_NUM ( ((N)-1)/2 + sizeof(unsigned)*8-1 )/(sizeof(unsigned)*8)
    #define GET_BITVALUE(p,idx) (((p)[((idx)/2-1)/(sizeof(unsigned)*8)]>>(((idx)/2-1)%(sizeof(unsigned)*8)))&1)
    #define SET_BITVALUE(p,idx) ((p)[((idx)/2-1)/(sizeof(unsigned)*8)] |= 1u<<(((idx)/2-1)%(sizeof(unsigned)*8)))

    unsigned* p = (unsigned*)calloc( UINT_NUM, sizeof(unsigned) );
    printf( "2" );
    for( unsigned i=3; i<=N; i+=2 )
    {
        if( GET_BITVALUE(p,i) )
            continue;

        printf( " %u", i );

        for( unsigned j=3*i; j<=N; j+=2*i )
            SET_BITVALUE(p,j);
    }
    free( p );

    return 0;
}
一共5761455个质数,最大的一个是99999989
2013-12-13 12:46
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
补充:
unsigned* p = (unsigned*)calloc( UINT_NUM, sizeof(unsigned) );
应该改为
unsigned* p = calloc( UINT_NUM, sizeof(unsigned) );

因为我在C++中也试验了一下,所以加了个强制转换,对C++而言这是必须的,否则无法编译通过。
但对C语言这样,这虽然符合语法,但属于不良习惯,带来了冗余陷阱。
2013-12-13 12:50
pavilion4994
Rank: 1
等 级:新手上路
帖 子:29
专家分:0
注 册:2013-10-17
收藏
得分:0 
非常感谢,是不是c里面就无法用大型数组了?那能用的数组最大能定义为多大?
2013-12-13 18:11
快速回复:大型数组筛法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017031 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved