UVA 11408 Count DePrimes (线性筛法)

于 2011年03月11日 发布在 算法&&ACM 跳到评论

UVA 11408 Count DePrimes

看到大牛的空间上有贴这个题的,我最近在看数论,所以就看了看O(n)线性筛法,没有花太长时间,不过感觉挺神奇的,我在内层循环里加了个count++来计算它的计算次数,没想到筛200万的素数count只有185万,好神奇。这个算法的思想就是避免重复筛,比如35=5*7,就被筛了两次,我们只让一个和数只被他最小的素因子晒到。1Y了,好高兴~

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#define SULEN 5000000
using namespace std;
bool flag[SULEN+1];
int prime[500001];
int sum[SULEN+1];
void xianxingshai(void)
{
    int count,i,j;
    fill( flag,flag+SULEN,true );
    fill( sum ,sum +SULEN, 0 );
    flag[0] = flag[1] = false;
    for( count = 0, i = 2; i <= SULEN; i++ )
    {
        if( flag[i] )
        {
            prime[count++] = i;
            sum[i] = i;//素数的质因子和为其本身
        }
        for( j = 0; j < count && i*prime[j] <= SULEN; j++ )
        {
            flag[ i*prime[j] ] = false;
            if( i%prime[j] == 0 ){
                sum[ i*prime[j] ] = sum[i];
                //已经有因子prime[j]时候,因子和就不加了,
                break;
            }
            else
                sum[ i*prime[j] ] = sum[ i ] + prime[j];
        }
    }
}
int main(void)
{
    init();
    int count,start,i,end;
    while( cin >> start && start )
    {
        cin >> end;
        for( count = 0,i = start; i <= end; i++ )
            if( flag[ sum[i] ] ) count++;
        cout << count << endl;
    }
    return 0;
}

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)