公式最核心是三个for循环

for(p=2;p*p<=n;next(x))
    for((q=p;p*p<=n;next(q)))
        for(m=p*q;m<=n;m=p*m)
            remove(m);

完整代码如下

#include<bits/stdc++.h>
#define MAXSIZE 1000
using namespace std;
int main(){
    int previous[MAXSIZE+1];
    int next[MAXSIZE+1];
    int prime,fact,i,mult;
    int n,count=0;
    char line[100],dummy;
    gets(line);
    n=strtoul(line,&dummy,10);
    for(i=2;i<=n;i++){
        previous[i]=i-1;
        next[i]=i+1;
    }
    previous[2]=next[n]=NULL;

    for(prime=2;prime*prime<=n;prime=next[prime])
        for(fact=prime;prime*fact<=n;fact=next[fact])
            for(mult=prime*fact;mult<=n;mult*=prime){
                next[previous[mult]]=next[mult];
                previous[next[mult]]=previous[mult];
            }
    return 0;
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注