当前位置:首页 > 数论 > 正文
POJ3292Semi-prime H-numbers(H-合成数)
219+

题目大意:4n+1成为H数,H数中如果一个数字如果找不到另一个H数(1除外)作为约数,那么他就是H素数(1除外),否则是H合数;如果一个H数是两个H素数的乘积,那么他就是H合成数;请问n以内有多少个H合成数?

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

解题思路

首先,求出n以内的所有H素数;接着,任意两个H素数相乘,得到的数字k就是H合成数(%4==1、两个H素数的乘积),标记f[k]=2;最后遍历f数组,有多少个2就有多少个合成数。

因为是多组数据,可能有大量重复运算,我们可以用前缀和预处理前i个数字中,有多少个H合成数。

程序实现

枚举4n+1,暴力枚举他的约数,如果没有约数就是H素数,放入s数组中。s数组中的任意两个数(可以相同)相乘得到H合成数k,标记f[k]=2;计算f[k]的“前缀和”,f[k]=1表示+1,其他情况表示0。

筛选法求H素数:H合数可以分解成H素数的乘积,每找到一个H素数,存入s数组,并将其倍数标记为H合数。j/i表示倍数,该倍数也应该是H数,故j/i % 4也应该等于1。当然,这个条件不写也没问题,因为如果倍数不是H数,乘积也不可能是H数:i是H素数,那么i*b%4 = i%4 * (b%4) = b%4,标记多了外重循环也不会遍历到他。

不难发现,加1次i、2次i、3次i、4次i、5次i……余数分别是2、3、0、1、2……只有加4次i才是有效的,每次加4i可以减少循环次数。

更多

About

坚决不Copy代码!

本文标签:,,,,,,,

POJ3292Semi-prime H-numbers(H-合成数):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter