C++问题：“H数”

描述
所谓H数，是指只含有2,3,5,7这些质因数的数，如630是H数，而22不是。现在要求输出第n个H数，为了方便起见将H[1]定为1。已知n不超过10000，最后数据在int64范围之内。

输入
一个正整数n（不超过10000）。
输出
第n个H数。

输入样例 1
1
输出样例1
1

输入样例 2
30
输出样例2
49

#include <iostream>
using namespace std;
bool isprime(int n)
{
    for (int i = 2; i < n / 2; i++)
        if (n % i == 0) return false;
    return true;
}
bool isH(int n)
{
if (n < 11) return true;
for (int i = 11; i <= n; i++)
if (isprime(i) && n % i == 0) return false;
return true;
}
int main()
{
int n;
cin >> n;
int cnt = 0;
for (int i = 1; 1; i++) 
{
if (isH(i)) cnt++;
if (cnt == n)
{
cout << i;
break;
}
}
return 0;
}
 

【以下回答由 GPT 生成】

解决方案

在编写C++程序解决这个问题之前，我们首先需要理解什么是H数。H数是指只包含质因数2、3、5、7的数。

为了计算第n个H数，我们可以使用动态规划的方法，通过不断更新已有的H数，来计算下一个H数。具体实现步骤如下：

1. 定义一个数组h，用来存储计算得到的H数。数组的初始值只有一个元素h[0] = 1。
2. 定义变量index，用来记录当前计算的是第几个H数。初始值为1。
3. 定义变量num，用来记录当前计算的H数。初始值为1。
4. 进入一个循环，循环条件为index < n，即继续计算下一个H数直到达到第n个。
5. 在循环中，计算下一个H数的值，即将数组h中的元素分别乘以2、3、5、7，并取最小值。
6. 将计算得到的下一个H数保存到数组h中，即h[index] = num。
7. 将index加1。
8. 重复步骤5至步骤8，直到计算出第n个H数为止。

下面是C++语言的实现代码：

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入一个正整数n: ";
    cin >> n;

    int h[10000];
    h[0] = 1;  // 初始化第一个H数为1
    int index = 1;  // 当前计算的是第几个H数
    int num = 1;  // 当前计算的H数

    while (index < n) {
        int temp = num;
        while (temp % 2 == 0) {
            temp /= 2;
        }
        while (temp % 3 == 0) {
            temp /= 3;
        }
        while (temp % 5 == 0) {
            temp /= 5;
        }
        while (temp % 7 == 0) {
            temp /= 7;
        }

        // 如果temp变为1，说明num只包含质因数2、3、5、7
        if (temp == 1) {
            h[index] = num;
            index++;
        }

        num++;
    }

    cout << "第" << n << "个H数：" << h[n-1] << endl;

    return 0;
}

输入示例1：

请输入一个正整数n: 1

输出示例1：

第1个H数：1

输入示例2：

请输入一个正整数n: 30

输出示例2：

第30个H数：49