POJ 3292-Semi-prime H-numbers（H半素数）

╰+哭是因爲堅強的太久メ 2022-07-10 04:55 167阅读 0赞

Semi-prime H-numbers

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;9289</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;4124</td> 
  </tr> 
 </tbody> 
</table>

Description

This problem is based on an exercise of David Hilbert, who pedagogically suggested that one study the theory of *4n+1* numbers. Here, we do only a bit of that.

An **H**\-number is a positive number which is one more than a multiple of four: 1, 5, 9, 13, 17, 21,... are the **H**\-numbers. For this problem we pretend that these are the *only* numbers. The **H**\-numbers are closed under multiplication.

As with regular integers, we partition the **H**\-numbers into units, **H**\-primes, and **H**\-composites. 1 is the only unit. An **H**\-number *h* is **H**\-prime if it is not the unit, and is the product of two **H**\-numbers in only one way: 1 × *h*. The rest of the numbers are **H**\-composite.

For examples, the first few **H**\-composites are: 5 × 5 = 25, 5 × 9 = 45, 5 × 13 = 65, 9 × 9 = 81, 5 × 17 = 85.

Your task is to count the number of **H**\-semi-primes. An **H**\-semi-prime is an **H**\-number which is the product of exactly two **H**\-primes. The two **H**\-primes may be equal or different. In the example above, all five numbers are **H**\-semi-primes. 125 = 5 × 5 × 5 is not an **H**\-semi-prime, because it's the product of three **H**\-primes.

Input

Each line of input contains an **H**\-number ≤ 1,000,001. The last line of input contains 0 and this line should not be processed.

Output

For each inputted **H**\-number *h*, print a line stating *h* and the number of **H**\-semi-primes between 1 and *h* inclusive, separated by one space in the format shown in the sample.

Sample Input

21 
    85
    789
    0

Sample Output

21 0
    85 5
    789 62

Source

[Waterloo Local Contest][], 2006.9.30

## 题目意思： ##

H数是比4的倍数多1的正数，例如：1,5,9,13,17,21，...都是H数，且H数在乘法下闭合。

与正整数一样，我们将H数分为“单位”，“H素数”和“H复合”。

①其中1是唯一的“单位”；

②如果不是单位，H数h是H-prime，并且是仅以一种方式的两个H数的乘积：1×h；

③其余的数字是H复合。  
例如，前几个H复合物是：5×5 = 25,5×9 = 45,5×13 = 65,9×9 = 81,5×17 = 85。

给出一个数N，你的任务是计算1~N中H半素数的个数。

H半素数是一个H数，它是两个H素数的乘积。两个H素数可以相等或不同。在上面的例子中，所有五个数字都是H半素数。

125 = 5×5×5不是H半素数，因为它是三个H素数的乘积。

## 解题思路： ##

根据题目对数的分类来打表…

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXN 1000010
    int sum=0;
    //0:H-prime
    //1:H-semi-primes
    //-1:H-composite
    int hprime[MAXN];
    
    void init()
    {
        memset(hprime,0,sizeof(hprime));
        for(int i=5; i<=MAXN; i+=4)
            for(int j=5; j<=MAXN; j+=4)
            {
                int t=i*j;
                if(t>MAXN)
                    break;
                if(hprime[i]==0&&hprime[j]==0) hprime[t]=1;//H-semi-primes
                else hprime[t]=-1;//H-composite
            }
        int sum=0;
        for(int i=1; i<=MAXN; i++)
        {
            if(hprime[i]==1) ++sum;
            hprime[i]=sum;//从1到i有sum个H-semi-primes
        }
        return;
    }
    
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        init();
        int n;
        while(cin>>n&&n)
        {
            cout<<n<<" "<<hprime[n]<<endl;
        }
        return 0;
    }
    /*
    21
    85
    789
    0
    */

[Waterloo Local Contest]: http://poj.org/searchproblem?field=source&key=Waterloo+Local+Contest