poj 3292 Semi-prime H-numbers 素数变形+打表+筛选法-白红宇

poj 3292 Semi-prime H-numbers 素数变形+打表+筛选法

阅读量：4113 次

发布时间：2019-05-25

本文共 1649 字，大约阅读时间需要 5 分钟。

题意：1,5,9,13....这些4*n+1数字组成了一个全集，输入一个数字，求<=该数字能够被两个”素数“相乘表示的

数字的个数，比如25=5*5,45=5*9,,（9也是”素数“）

#include 
     
       #include
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int infpi=acos(-1); const int maxn=1e6+1; int num[maxn],flag[maxn]; void init() { for(int i=5;i<=maxn;i+=4) for(int j=5;j<=maxn;j+=4) { if((ll)(i*j)>maxn) break; if(flag[i]||flag[j]) continue; flag[i*j]=1; } int cnt=0; for(int i=2;i<=maxn;i++) { if(flag[i]) cnt++; num[i]=cnt; } } int main() { init(); int n; while(cin>>n&&n) printf("%d %d\n",n,num[n]); return 0; }

错因分析：没有好好体会筛选法的实质，这道题能很好的训练队筛选法的理解；

#include 
     
       #include
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int infpi=acos(-1); const int maxn=1e6+1; int num[maxn+5],flag[maxn+5]; void init() { for(int i=5;i<=maxn;i+=4) for(int j=5;j<=maxn;j+=4) { ll temp=i*j; if(temp>maxn) break; if(flag[i]==0&&flag[j]==0)//0代表素数，1即是所求，-1不是所求 flag[temp]=1; else flag[temp]=-1; } int cnt=0; for(int i=0;i<=maxn;i++) { if(flag[i]==1) cnt++; num[i]=cnt; } } int main() { init(); int n; while(cin>>n&&n) printf("%d %d\n",n,num[n]); return 0; }