学步园

有一组数列，1, 5, 9, 13, 17, 21,25...，（都模4余1），叫做H数列。
可以把H数列中的数分为三种
（1）H-素数：h是H-素数，把h是分解成两个数（这两个数都是H数列中的数）的积的形式，只有一种是就是h=h*1；（即h在H数列中找不到除了本身和1的因数）
（2）H-合数：不是1，不是H-素数，就是H-合数；
（3）单位数：只有1一个；
现在（在数列H中）定义一个H-半素数：如果h是H-半素数，当且仅当h能表示成两个H-素数的积的形式，这两个H-素数可以相等，例如25=5*5,（5是H-素数，25是H-半素数），45=5*9（5和9是H-素数，45是H-半素数）；

每行输入一个整数n，（n<=1000001）要求输出出小于等于n的半素数的个数。
最后一行以0结尾，此行不处理。

每行对应输出小于等于n的半素数的个数。

21 
85
789
0

0
5
62

题目大意：求解前n个H半素数的个数；

解题思路：根据对4余1，H数列的定义。H素数是对H数列的互素。也就是说，可以根据H素列进行线性筛选H半素数。如何筛选呢？

本人思路：

第一步：建立数组，存H素列；

第二步：根据H素列筛掉H半素数；

第三步：在筛半素数的时候，进行统计；

第四步：输出结果；

#include<stdio.h> 
#include<math.h> 
#include<string.h> 
#define MAX 1000001 
int prime[80000]; 
bool is_not_prime[MAX]; 
void init(int n) 
{ 
    int i,j,r; 
    int num=0; 
    int num_prime=0; 
    memset(is_not_prime,false,sizeof(is_not_prime));//清零 
    for(i=5; i<=n; i+=4) //这是代表H数列
    { 
        if(!is_not_prime[i]) //这里筛出了H素列
        { 
            prime[num_prime++]=i; //存入H素列，num_prime存的是H素列数组里的H素数的个数
        } 
        for(j=0; j<=num_prime&&i*prime[j]<=n; j++) //开始筛选出H半素数
        { 
            if(is_not_prime[i*prime[j]])continue; //假如以前i*prime[j]这个数已经统计过了，他是合数(是不是H半素数也已经判断了)。那么就不再统计第二遍了,例如：21*21和9*49结果都是441，但是21，9，49都是H素列，所以会导致num多加一次，所以要舍去。
            is_not_prime[i*prime[j]]=true; //标记合数，i*prime[j]一定是合数，但是他也可能是H半素数，所以下面进行判断
             if(!is_not_prime[i]&&!is_not_prime[prime[j]])//i和prime[j]都是H素数，那么i*prime[j]就是H素数 
                { 
                    num++; //统计H素数的个数
                } 
            //if(!(i%prime[j]))break;//这里就是相当于剪枝了，但是个人感觉对于这个线性筛没必要，加这句，假如是i=125,prime[0]=5；那么i*prime[0]=625;而假如没这个判断那么在i=25,prime[j]要等于25 而25不是H素数，所以不构成多重判。故没必要加上这句。若是线性筛选素数，则必须加，例子如上。 
        } 
    } 
    printf("%d\n",num); 
} 
int main() 
{ 
    int m; 
    while(~scanf("%d",&m)) 
    { 
        if(m==0)break; 
        init(m); 
    } 
    return 0; 
} 
/************************************************************** 
    Problem: 1614 
    User: 201141919106 
    Language: C++ 
    Result: Accepted 
    Time:10 ms 
    Memory:2348 kb 
****************************************************************/