oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

线性筛素数方法

Posted on 2008-06-04 16:39 oyjpart 阅读(9087) 评论(18)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛
看到高手的线性筛素数方法(Prime2函数):

const int N = 25600000;
bool a[N];
int p[N];
int n;

void Prime1() {
    memset(a, 0, n * sizeof(a[0]));
    int num = 0, i, j;
    for(i = 2; i < n; ++i) if(!a[i]) {
        p[num++] = i;
        for(j = i+i; j < n; j +=i) {
            a[j] = 1;
        }
    }
}

void Prime2() {
    memset(a, 0, n*sizeof(a[0]));
    int num = 0, i, j;
    for(i = 2; i < n; ++i) {
        if(!(a[i])) p[num++] = i;
        for(j = 0; (j<num && i*p[j]<n); ++j) {
            a[i*p[j]] = 1;
            if(!(i%p[j])) break;
        }
    }
}

测试:

筛 [0, 100000) 范围内的素数
第一种素数筛法 0 毫秒
第二种素数筛法 0 毫秒

筛 [0, 200000) 范围内的素数
第一种素数筛法 15 毫秒
第二种素数筛法 0 毫秒

筛 [0, 400000) 范围内的素数
第一种素数筛法 16 毫秒
第二种素数筛法 15 毫秒

筛 [0, 800000) 范围内的素数
第一种素数筛法 47 毫秒
第二种素数筛法 16 毫秒

筛 [0, 1600000) 范围内的素数
第一种素数筛法 62 毫秒
第二种素数筛法 63 毫秒

筛 [0, 3200000) 范围内的素数
第一种素数筛法 297 毫秒
第二种素数筛法 109 毫秒

筛 [0, 6400000) 范围内的素数
第一种素数筛法 922 毫秒
第二种素数筛法 266 毫秒

筛 [0, 12800000) 范围内的素数
第一种素数筛法 2187 毫秒
第二种素数筛法 563 毫秒

筛 [0, 25600000) 范围内的素数
第一种素数筛法 4828 毫秒
第二种素数筛法 1187 毫秒

证明:任何一个合数只被标记一次。
      可以试着执行下这个程序的流程,就明白了

怎么样 还行吧?
什么,觉得这个程序效率上没多大提升,没有什么用?
把a[]改成int类型,然后
void Prime2() {
    memset(a, 0, n*sizeof(a[0]));
    int num = 0, i, j;
    for(i = 2; i < n; ++i) {
        if(!(a[i])) p[num++] = i;
        for(j = 0; (j<num && i*p[j]<n && (p[j]<=a[i]||a[i]==0)); ++j) {
            a[i*p[j]] = p[j];
        }
    }
}
这样一来a[i]将记录i的最小质因子
那么[0, n)内的数的因式分解就可以... 嘿嘿
o(质因子个数)求任意数因式分解:
void factor(int x) {
    while(a[x] != 0) {
        printf("%d\n", a[x]);
        x /= a[x];
    }
    printf("%d\n", x);


然后用这个做了上次杭州比赛的GCD那题,虽然其实就是个容斥原理,可是我等白菜就是不会做。唉。
第一名8题,我们4题,这个差距大的有点想吐。
题目http://acm.hdu.edu.cn/showproblem.php?pid=1695
//Solution by alpc12:

#include 
<string.h>
#include 
<stdio.h>

const int N = 100010;

typedef __int64 LL;
#define I64Format 
"%I64d\n"
inline 
int count(int x) {int ret = 0;while(x != 0) {ret ++; x &= (x-1);}return ret;}

int a[N], p[18000];

void pre() {
    memset(a, 
0, sizeof(a));
    
int num = 0, i, j;
    
for(i = 2; i < N; ++i) {
        
if(!a[i])  p[num++= i;
        
for(j = 0; j < num && i * p[j] < N && (p[j]<=a[i] || a[i]==0); ++j) {
            a[p[j] 
* i] = p[j];
        }
    }
}

void go(int x, int y) {
    
if(x == 0) { printf("0\n"); return; }
    
int i, j;
    LL ans 
= 0;
    
for(i = 1; i <= y; ++i) {
        
if(!a[i]) {
            ans 
+= (i<=x?(i-1):x);
        } 
else {
            
int fac[20], nfac = 0, z = i;
            
while(a[z] != 0) {
                fac[nfac
++= a[z];
                z 
/= a[z];
            }
            fac[nfac
++= z;
            
int k = 1;
            
for(j = 1; j < nfac; ++j) {
                
if(fac[j] != fac[j-1])
                    fac[k
++= fac[j];
            }
            nfac 
= k;
            
int now = 0;
            
int xx = x;
            
if(x >= i) xx=i-1;
            
int mask;
            
for(mask = 1; mask < (1<<nfac); ++mask) {
                
int d = count(mask), mul = 1;
                
for(j = 0; j < nfac; ++j) if((mask&(1<<j)) != 0) {
                    mul 
*= fac[j];
                }
                
if(d&1) now += xx/mul;
                
else now -= xx/mul;
            }
            ans 
+= xx-now;
        }
    }
    printf(I64Format, 
1+ans);
}

int main() {

//    freopen("t.in", "r", stdin);

    
int ntc, a, b, c, d, k;
    scanf(
"%d"&ntc);
    pre();
    
int tc = 0;
    
while(ntc--) {
        printf(
"Case %d: "++tc);
        scanf(
" %d %d %d %d %d"&a, &b, &c, &d, &k);
        
if(k == 0) printf("0\n");
        
else {
            a 
= b/k;
            b 
= d/k;
            
if(a > b) go(b, a);
            
else go(a, b);
        }
    }
    
return 0;
}


Feedback

# re: 线性筛素数方法  回复  更多评论   

2008-06-05 12:29 by Navi
void Prime1() {
memset(a, 0, n * sizeof(a[0]));
int num = 0, i, j;
for(i = 2; i < n; ++i) if(!a[i]) {
p[num++] = i;
for(j = i+i; j < n; j +=i) {
a[j] = 1;
}
}
}


这个for (j = i + i)应该是i * i吧

# re: 线性筛素数方法  回复  更多评论   

2008-06-05 20:25 by Griffin
不懂就别评论
虽然很无聊,但是可以说一句,i<<1的效率还要比i+i略高那么一点点点

# re: 线性筛素数方法  回复  更多评论   

2008-06-05 20:43 by oyjpart
呵呵~~

# re: 线性筛素数方法  回复  更多评论   

2008-06-11 19:07 by 小Young
经典啊,小地方也有精妙方法!

# re: 线性筛素数方法  回复  更多评论   

2008-06-21 13:43 by owen
我才发现以前我做素数表的方法这么土。

# re: 线性筛素数方法  回复  更多评论   

2008-06-21 22:11 by oyjpart
呃 ...

# re: 线性筛素数方法  回复  更多评论   

2008-07-16 18:51 by ktpime
性能太差, 下次发一个一秒筛20亿的
这不是危言耸听

# re: 线性筛素数方法  回复  更多评论   

2008-07-16 23:56 by oyjpart
好,记得发啊

# 佩服 ALPC, 赞  回复  更多评论   

2008-07-25 22:22 by ecnu
太强大了....

# re: 线性筛素数方法  回复  更多评论   

2008-07-26 06:10 by lengbufang
看看!

# re: 线性筛素数方法  回复  更多评论   

2008-08-21 16:39 by Awaken
@Navi
就应该是i+i
最小的是i的2倍

# re: 线性筛素数方法  回复  更多评论   

2008-11-16 23:02 by temp
@Griffin
自己不懂,别说别人不懂,明明i*i可以效率更高...

# re: 线性筛素数方法  回复  更多评论   

2008-11-16 23:59 by oyjpart
额??i*i??

# re: 线性筛素数方法  回复  更多评论   

2008-12-08 18:04 by lala
@temp
你比较傻

# re: 线性筛素数方法  回复  更多评论   

2009-01-05 11:30 by 周志鹏
prime2的确很强大,聪明,
我有个改进的地方,见笑啦:
void Prime3() {
memset(a, 0, n*sizeof(a[0]));
int num = 0, i, j;
p[num++]=2;a[2*2]=1;
for(i = 3; i < n; i+=2) {
if(!(a[i])) p[num++] = i;//i是素数就标记
for(j = 0; (j<num && i*p[j]<n); ++j) {
a[i*p[j]] = 1;
if(!(i%p[j])) break;//i是合数则跳出
}
}
}

# re: 线性筛素数方法  回复  更多评论   

2009-01-05 15:01 by oyjpart
呵呵 不错,是改进。

# re: 线性筛素数方法  回复  更多评论   

2010-04-01 16:24 by TonyShaw
@周志鹏
@Griffin
@Awaken
@temp
@lala
i*i没错,对于一个数x,假设它含有质因子i,那么令y=x/i;可以发现,如果所有小于i*i的含有因子i的数字,其y值小于i,这样的话,在以前的筛选过程中,就会把x筛掉,所以没有必要重新筛选一遍,仅需从sqr(i)到n即可。

# re: 线性筛素数方法[未登录]  回复  更多评论   

2011-07-02 16:10 by 。。。。
@lala
显然,i*i是对的,原因自己看算法竞赛与入门经典,另外其实,第一重循环的i,是可以按2,4步长增加的,。。。。。不解释

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理