看到大牛的空间上有贴这个题的,我最近在看数论,所以就看了看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; }