UVA 11408 Count DePrimes (线性筛法)

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;
}