Hi everyone,

Well the problem which I'm going to discuss here is from USACO Chapter 3.

The problem description is given below:

For a given set of K prime numbers S = {p₁, p₂, ..., p_K}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p₁, p₁p₂, p₁p₁, and p₁p₂p₃ (among others). This is the set of `humble numbers' for the input set S. Note: The number 1 is explicitly declared not to be a humble number.

Your job is to find the Nth humble number for a given set S. Long integers (signed 32-bit) will be adequate for all solutions.

K and N, 1 <= K <=100 and 1 <= N <= 100,000.

 I'm getting TLE due to running O(N ^ 2 * K) algorithm (Simply I'm building the humble number sequence
starting at 1 then at each iteration find the minimum number which is bigger than the last found humble number).

Am i missing something? Or is there a better algorithm for solving this problem?


Thanks in advance.


Igor.