poj3292-Semi-prime H-numbers(筛法打表)

一，题意：
　　一个H-number是所有的模四余一的数。(x=4*k+1)
　　如果一个H-number是H-primes 当且仅当它的因数只有1和它本身（除1外）。
　　一个H-number是H-semi-prime当且仅当它只由两个H-primes的乘积表示。
　　H-number剩下其他的数均为H-composite。
　　给你一个数h,问1到h有多少个H-semi-prime数。
二，思路：
　　1，打表;
　　2，记数，并储存;
　　3，输出;
三，步骤：
　　1，打H-semi-prime表
　　　　i,初始化H_number[]等于零;
　　　　ii,双重循环判断 number[i]和number[j]都等于0时
　　　　　　(即i和j是H-primes时), H_number[i*j]等于1;
　　　　　　否则等于-1(即i和j有一个不是H-primes);
　　2，记录H-semi-prime的个数，并存入对应的数组元素中;
　　3，直接输出 H_number[] 数组元素即可

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int N = 1000010;
 5 int H_number[N];
 6 
 7 void print_H_number(){
 8     memset(H_number, 0, sizeof(H_number)); 
 9     for(int i = 5 ; i < N ; i+=4){
10         for(int j = 5 ; j < N ; j+=4){
11             if(i*j>N)break;                 //防止越界 
12             if(H_number[j]==0&&H_number[i]==0) //表示i和j都是H-primes
13                 H_number[i*j]=1;            //标识 1 表示时是 H-semi-prime
14             else 
15                 H_number[i*j]=-1;    // 表示i和j有一个不是H-primes 所做的标识 
16         }
17     }
18 }
19 
20 void work(){
21     int count=0;
22     for(int i = 1 ; i < N ; i++){
23             if(H_number[i]==1)count++;    //记录 H-prime 的个数 
24             H_number[i]=count;             //将每个范围中的 H-prime 个数存入对应的数组元素中 
25     }
26 }
27 
28 int main(){
29     int n ; 
30     print_H_number();
31     work(); 
32     while(cin>>n,n){
33         cout<<n<<" "<<H_number[n]<<endl;
34     }
35     return 0;
36 }

View Code