Finding solutions for a given pair (number of factors, number of prime factors)

Question

I have been given x and k, where x is the number of factors of a number A, and k is the number of prime factors of A. Given x and k, I have to find out whether such an A exists.

For example:

INPUT : 4 2 
OUTPUT : 1

Since 6 is a number that has 4 factors 1, 2, 3, 6 out of which 2 are prime(2, 3). Also it is given that x and k can have any values between 1 and 10⁹.

Here is my code for the this:

long long int x, k;
scanf("%lld%lld", &x, &k);

int ans = 0;

bool stop = false;

for (long long int numbers = 1; numbers < pow(10, 9) && !stop; numbers++) {
    long long int noOfFactors = 0, noOfPrimes = 0;
    for (long long int a = 1; a <= numbers && !stop; a++) {
        if (numbers % a == 0) {
            noOfFactors += 1;
            if ((isprime(a)) == 1) {
                noOfPrimes += 1;
            }
         }
     }
     if (noOfFactors == x && noOfPrimes == k) {
         ans = 1;
         stop = true;
     } else
         ans = 0;
}   
printf("%d\n", ans);

Where isprime(x) returns 1 if x is prime else 0.

But while running the program, it shows TLE error. Can anyone help me out in optimising this algorithm, or if any other method exists, can you just explain it to me ? Any help in optimising this algorithm or using another method would be kindly appreciated.

Answer 1

Let p₁, p₂, p₃, … p_k be the prime factors of some positive integer n. By the fundamental theorem of arithmetic, n can be represented as p₁^e₁•p₂^e₂•p₃^e₃• … p_k^e_k for some positive integers e₁, e₂, e₃, … e_k. Furthermore, any such set of such positive integers represents one positive integer in this way.

Every factor of n can be represented as p₁^f₁•p₂^f₂•p₃^f₃• … p_k^f_k for some integers f_i where 0 ≤ f_i ≤ e_i.

Each f_i can have e_i+1 values from 0 to e_i, so the number of factors of n is (e₁+1)•(e₂+1)•(e₃+1)• … (e_k+1).

Since each e_i must be positive, each e_i+1 must be at least 2. Now we can see that, if n has x factors, then x is expressible as a product of k integers each at least 2. Conversely, if x is expressible as a product of k integers each at least 2, that product gives us values for e_i, which gives us a positive integer n that has x factors and k prime factors.

Therefore, a number with x factors and k prime factors exists if and only if x is expressible as a product of k integers each at least 2.

To test this, simply divide x by prime numbers, e.g., divide by 2 as many times as possible without a remainder, then by 3, then by 5, and so on. Once x has been divided by k−1 factors and the result is greater than 1, then we know x is expressible as a product of k integers each at least 2 (the last may be composite rather than a prime, such as 2•3•3•3•35). If x reaches 1 before or just as we have divided it by k−1 factors, then no such number exists.

Addendum

Thinking about it further, it is not necessary to use prime numbers as candidates when testing x for factors. We can simply iterate through the integers, testing whether each candidate f is a factor of x. Trying to filter these by first testing whether f is prime would take more time than simply testing whether f is a factor of x. (This is not to say some more sophisticated method of testing x for prime factors, such as using a prepared table of many primes, would not be faster.) So the following code suffices.

#include <stdint.h>


/*  Return true if and only if there exists a positive integer A with exactly
    x factors and exactly k prime factors.
*/
static _Bool DoesAExist(uintmax_t x, uintmax_t k)
{
    /*  The only positive integer with no prime factors is 1.  1 has exactly
        one factor.  So, if A must have no prime factors (k is zero), then an A
        exists if and only if x is one.
    */
    if (k == 0) return x == 1;

    /*  A number with exactly one prime factor (say p) has at least two factors
        (1 and p) and can have any greater number of factors (p^2, p^3,...).
        So, if k is one, then an A exists if and only if x is greater than one.
    */
    if (k == 1) return 1 < x;

    /*  Otherwise, an A exists only if x can be expressed as the product of
        exactly k factors greater than 1.  Test this by dividing x by factors
        greater than 1 until either we have divided by k-1 factors (so one
        more is needed) or we run out of possible factors.

        We start testing factors with two (f = 2).

        If we find k factors of x during the loop, we return true.

        Otherwise, we continue as long as there might be more factors.  (When
        f*f <= x is false, we have tested the current value of x by every
        integer from two to the square root of x.  Then x cannot have any more
        factors less than x, because if there is any factorization x = r*s,
        either r or s must be less than or equal to the square root of x.)

        For each f, as long as it is a factor of the current value of x and we
        need more factors, we divide x by it and decrement k to track the
        number of factors still required.
    */
    for (uintmax_t f = 2; f*f <= x; ++f)
        while (x % f == 0)
        {
            /*  As long as f is a factor of x, remove it from x and decrement
                the count of factors still needed.  If that number reaches one,
                then:

                    If the current value of x exceeds one, it serves as the
                    last factor, and an A exists, so we return true.

                    If the current value of x exceeds one, there is no
                    additional factor, but we still need one, so no A exists,
                    so we return false.
            */
            x /= f;
            if (--k <= 1) return 1 < x;
        }

    /*  At this point, we need k more factors for x, and k is greater than one
        but x is one or prime, so x does not have enough factors.  So no A with
        the required properties exists, and we return false.
    */
    return 0;
}


#include <stdio.h>


int main(void)
{
    printf("False test cases:\n");
    printf("%d\n", DoesAExist(0, 0));   //  False since each positive integer has at least one factor (1).
    printf("%d\n", DoesAExist(2, 0));   //  False since no number has two factors and no prime factors.

    printf("%d\n", DoesAExist(0, 1));   //  False since each positive integer has at least one factor (1).
    printf("%d\n", DoesAExist(1, 1));   //  False since each positive integer with a prime factor has at least two factors (one and the prime).
    printf("%d\n", DoesAExist(2, 2));   //  False since each number with two prime factors (p and q) has at least four factors (1, p, q, and pq).
    printf("%d\n", DoesAExist(3, 2));   //  False since each number with two prime factors (p and q) has at least four factors (1, p, q, and pq).

    printf("%d\n", DoesAExist(8, 4));

    printf("%d\n", DoesAExist(6, 3));
    printf("%d\n", DoesAExist(22, 3));

    printf("%d\n", DoesAExist(24, 5));
    printf("%d\n", DoesAExist(88, 5));
    printf("%d\n", DoesAExist(18, 4));
    printf("%d\n", DoesAExist(54, 5));
    printf("%d\n", DoesAExist(242, 4));
    printf("%d\n", DoesAExist(2662, 5));

    printf("True test cases:\n");
    printf("%d\n", DoesAExist(1, 0));   //  True since 1 has one factor and zero prime factors.
    printf("%d\n", DoesAExist(2, 1));   //  True since each prime has two factors.
    printf("%d\n", DoesAExist(3, 1));   //  True since each square of a prime has three factors.
    printf("%d\n", DoesAExist(4, 1));   //  True since each cube of a prime has three factors.
    printf("%d\n", DoesAExist(4, 2));   //  True since each number that is the product of two primes (p and q) has four factors (1, p, q, and pq).

    printf("%d\n", DoesAExist(8, 2));
    printf("%d\n", DoesAExist(8, 3));

    printf("%d\n", DoesAExist(6, 2));
    printf("%d\n", DoesAExist(22, 2));

    printf("%d\n", DoesAExist(24, 2));
    printf("%d\n", DoesAExist(24, 3));
    printf("%d\n", DoesAExist(24, 4));
    printf("%d\n", DoesAExist(88, 2));
    printf("%d\n", DoesAExist(88, 3));
    printf("%d\n", DoesAExist(88, 4));
    printf("%d\n", DoesAExist(18, 2));
    printf("%d\n", DoesAExist(18, 3));
    printf("%d\n", DoesAExist(54, 2));
    printf("%d\n", DoesAExist(54, 3));
    printf("%d\n", DoesAExist(54, 4));
    printf("%d\n", DoesAExist(242, 2));
    printf("%d\n", DoesAExist(242, 3));
    printf("%d\n", DoesAExist(2662, 2));
    printf("%d\n", DoesAExist(2662, 3));
    printf("%d\n", DoesAExist(2662, 4));
}

Answer 2

First your implementation is too inefficient

• Don't call a function inside the for loop like this

  for (long long int numbers = 1; numbers < pow(10, 9) && !stop; numbers++)
  

  pow will be called unnecessarily on each iteration. Save every constant to a variable before the loop. But in this case just use numbers < 1e9

• To get all factors of n you just need to loop until sqrt(n). You're doing for (long long int a = 1; a <= numbers && !stop; a++) { if (numbers % a == 0) { so for example instead of only 10⁴ loops for 10⁸ you'll need 10⁸ loops. If numbers % a == 0 then both a and numbers/a are factors of numbers

But the real issue here is that your algorithm is flawed. You can get all factors of A if you know the prime factors of A and their exponents. If A = p₁^m p₂ⁿ ... p_k^p then A will have the following factors:

• p₁ⁱ for i = 1..m
• p₂ⁱ for i = 1..n
• ...
• p_kⁱ for i = 1..p
• Factors from 2 prime factors: p₁ⁱp₂^j, p₁ⁱp₃^j,... p₁ⁱp_k^j, p₂ⁱp₃^j, p₂ⁱp₄^j,... p₂ⁱp_k^j,... p_k-1ⁱp_k^j
• Factors from 3 prime factors...
• Factors from k prime factors

This is purely a combination counting issue that can be done easily without even knowing A. Notice that the number of factors from k prime factors has some relation to the number of factors from k-1 prime factors

Answer 3

Your algorithm is very inefficient. Here are a few ideas:

• reject obvious fails: if x < 2 or k <= 0 or x < k the answer is 0 without further testing.
• do not mix floating point and integer arithmetics. Use 1000000000 instead of pow(10, 9).
• the inner loop can be stopped much earlier than you do: only run it while a * a < numbers and add 2 divisors for each match. Add another divisor if a * a == numbers.
• also stop the inner loop if noOfFactors > x or noOfPrimes > k.

The program will run faster, but it is still not the right approach as the solution A might be much larger than the range of the integer types. For example x = 1000, k = 1 has an infinite number of solutions A = p⁹⁹⁹ for any prime p. Finding this solution via enumeration is impossible.

Analyzing the problem mathematically: the total number of factors for a number A that has k prime factors is (e₁+1)(e₂+1)...(e_k+1), where e_i is the power of its i-th prime factor, ie: A = Prod(p_i^e_i).

For a solution to exist, x must be the product of at least k factors. A modified version of a factoring loop can determine if at least k factors can be found whose product equals x.

Here is a simple program using this approach, that completes as soon as k factors have been found:

#include <stdio.h>

int test(unsigned int x, unsigned int k) {
    if (k == 0) {
        /* k is not supposed to be 0, but there is a single number A
           with no prime factors and a single factor: A = 1 */
        return x == 1;
    }
    if (x > k && k > 1) {
        for (unsigned int p = 2; x / p >= p;) {
            if (x % p == 0) {
                x /= p;
                if (--k == 1)
                    break;
            } else {
                /* skip to the next odd divisor */
                p += 1 + (p & 1);
            }
        }
    }
    return k == 1 && x > 1;
}

int main() {
    unsigned int x, k;

    while (scanf("%u%u", &x, &k) == 2)
        printf("%d\n", test(x, k));

    return 0;
}