程序代码：

const int UPBOUND = 100000;
int a[UPBOUND];
int p[UPBOUND],pn;

//号称线性的筛素数算法，实际性能确实不错 
//p[]={2,3,5,7,...},pn为小于UPBOUND的素数个数 
//若i是合数a[i]为i的最小因子，若i是素数a[i]=0 
void primefilter(){
    int i, j;
    for(i = 2; i < UPBOUND; ++i){
        if(!(a[i])) p[pn++] = i;
        for(j = 0; (j<pn && i*p[j]<UPBOUND && (p[j]<=a[i]||a[i]==0)); ++j) {
            a[i*p[j]] = p[j];
        }
    }
}