c - 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
", 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:
");
    printf("%d
", DoesAExist(0, 0));   //  False since each positive integer has at least one factor (1).
    printf("%d
", DoesAExist(2, 0));   //  False since no number has two factors and no prime factors.

    printf("%d
", DoesAExist(0, 1));   //  False since each positive integer has at least one factor (1).
    printf("%d
", DoesAExist(1, 1));   //  False since each positive integer with a prime factor has at least two factors (one and the prime).
    printf("%d
", 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
", 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
", DoesAExist(8, 4));

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

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

    printf("True test cases:
");
    printf("%d
", DoesAExist(1, 0));   //  True since 1 has one factor and zero prime factors.
    printf("%d
", DoesAExist(2, 1));   //  True since each prime has two factors.
    printf("%d
", DoesAExist(3, 1));   //  True since each square of a prime has three factors.
    printf("%d
", DoesAExist(4, 1));   //  True since each cube of a prime has three factors.
    printf("%d
", 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
", DoesAExist(8, 2));
    printf("%d
", DoesAExist(8, 3));

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

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