Semi-prime H-numbers UVA - 11105（筛选假素数）

#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
const int maxn=1e6+10;

bool vis[maxn];
ll cnt_pri,pri[maxn];
void init(int n){
    //这个筛选的方法效率太低了
    /*
    cnt_num=0;
    for(int i=1;i<=n;i+=4){
        num[cnt_num++]=i;
    }
   // printf("cnt_num:%d\n",cnt_num);
    cnt_pri=0;
    for(int i=0;i<cnt_num;i++){
        pri[cnt_pri++]=num[i];
        for(int j=1;num[j]*num[j]<=num[i];j++){
            if(num[i]%num[j]==0){
                cnt_pri--;break;
            }
        }
    }
  //  printf("cnt_pri:%d\n",cnt_pri);
   // rep(i,0,10)    printf("i:%d %d\n",i,pri[i]);
    */
    //这个筛”素数“ 是真的强，我还先把素数找出来，然后再去判断，可不可以
    //
    for(int i=5;i<=n;i+=4){
        if(vis[i])continue;
        pri[cnt_pri++]=i;
        for(int j=2*i;j<=n;j+=i){//肯定是包含，我们要删的点的，只不过会多删掉一些点
            vis[j]=true;
        }
    }
    //printf("cnt:%d\n",cnt_pri);
    //rep(i,0,10)    printf("i:%d %d\n",i,pri[i]);
}

/*
还是一道因子的题，筛‘’素数‘’的效率问题
还有就是枚举的问题  1e3*(log(n)||n)的复杂度，完全可以解决
坑点:恐怕自己做的时候，重复问题，不会注意把，因为素数怎么会有重复的，但他不是素数，它是假的，新的定义
*/

int main(){
    //freopen("123.txt","w",stdout);
    //double t1=clock();
    init(1e6+1);
    //printf("%.2f\n",(clock()-t1)/CLOCKS_PER_SEC);
    int n;
    while(scanf("%d",&n)==1&&n){
        int ans=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<cnt_pri;i++){
            if(pri[i]*pri[i]>n)break;
            for(int j=i;j<cnt_pri;j++){
                ll sum=pri[i]*pri[j];
                //printf("sum:%lld\n",sum);
                if(sum>n)break;
                if(vis[sum])continue;
                ans++;
                vis[sum]=true;
            }
        }
        printf("%d %d\n",n,ans);
    }
    return 0;
}