Semi-prime H-numbers POJ - 3292 (数学打表)

淡淡的烟草味﹌ 2022-02-20 13:48 220阅读 0赞

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

解题思路:

暴力打表,从5开始枚举,步长为4:这样得到的枚举结果是H数

将H数两两相乘,如果乘数都为H质数,那么结果就是半H质数

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <math.h>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    const int MAXN = 1000010;
    int N;
    int is_primes[MAXN];
    int tanses[MAXN];
    void getTables() {
    	for (int i = 5; i <= MAXN; i+=4) {
    		for (int j = 5; j <= MAXN; j+=4) {
    			int mulres = i * j;
    			if(mulres > MAXN) break;  //超出范围就退出
    			if (is_primes[i]==0 && is_primes[j]==0) {   //如果两个都是质数
    				is_primes[mulres] = 1;
    			}
    			else {
    				is_primes[mulres] = -1;   //为什么设置为-1?因为它已经是两个数的乘积,不满足条件
    			}
    		}
    	}
    	int tans = 0;
    	for (int k = 1; k <= MAXN; ++k) {
    		if (is_primes[k]==1) {
    			tans++;
    		}
    		tanses[k] = tans;
    	}
    }
    
    int main() {
    	memset(is_primes, 0, sizeof(is_primes)); 
    	getTables();  //打表
    	while (scanf("%d", &N) != EOF) {
    		if(N == 0) break;
    		printf("%d %d\n", N, tanses[N]);  
    	}
    
    	system("PAUSE");
    	return 0;
    }