Project Euler 204

题目

Generalised Hamming Numbers

A Hamming number is a positive number which has no prime factor larger than 5.

So the first few Hamming numbers are $1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15$.

There are $1105$ Hamming numbers not exceeding $10^8$.

We will call a positive number a generalised Hamming number of type $n$, if it has no prime factor larger than $n$.

Hence the Hamming numbers are the generalised Hamming numbers of type $5$.

How many generalised Hamming numbers of type $100$ are there which don’t exceed $10^9$?

解决方案

令$N=100,M=10^9$，$N$以内的质数存放在数组$pr$中，一共有$m$个。

基本思想是：先产生有小质因子的合数，再利用这些小质因子的质数产生含有大质因子的合数。

假设数组$g[i]$存放由第$1\sim i$个质因数构成的广义汉明数，那么尝试将$g[i]$中的所有数都乘以$pr[i+1]^0,pr[i+1]^1,pr[i+1]^2,\dots$，将产生的这些数存放到数组$g[i+1]$中。

枚举发现，数组$g[m]$中的广义汉明数不多。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100;
const ll M = 1e9;
vector<int>a,pr;
bool vis[N+4];
int main() {
    for (int i = 2; i <= N; i++) {
        if (vis[i]) continue;
        pr.push_back(i);
        for (int j = i * i; j <= N; j += i)
            vis[j] = true;
    }
    a.push_back(1);
    for (int p: pr) {
        int m = a.size();
        for (int i = 0; i < m; i++) {
            for (ll x = 1ll * a[i] * p; x <= M; x *= p)
                a.push_back(x);
        }
    }
    int ans = a.size();
    printf("%d\n", ans);
}