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

by


Let p1, p2, p3, … pk be the prime factors of some positive integer n. By the fundamental theorem of arithmetic, n can be represented as p1e1•p2e2•p3e3• … pkek for some positive integers e1, e2, e3, … ek. Furthermore, any such set of such positive integers represents one positive integer in this way.

Every factor of n can be represented as p1f1•p2f2•p3f3• … pkfk for some integers fi where 0 ≤ fi ≤ ei.

Each fi can have ei+1 values from 0 to ei, so the number of factors of n is (e1+1)•(e2+1)•(e3+1)• … (ek+1).

Since each ei must be positive, each ei+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 ei, 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));
}

1

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