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