令 p 1， p 2， p 3，… p k 为某个正整数 n
的素因子。由算术基本定理，
Ñ 可以被表示为 p 1 ë 1 • p 2 ë 2 • p 3 é 3 •… p ķ Ë ķ 一些正整数
ë 1， ë 2， ë 3，… Ë ķ 。此外，这种正整数的任何这样的集合以这种方式表示一个正整数。

的各因素 Ñ 可以被表示为 p 1 ˚F 1 • p 2 ˚F 2 • p 3 ˚F 3 •… p ķ ˚F
ķ 对于某些整数 ˚F 我 其中0≤ ˚F 我 ≤ ë 我 。

每个 f i 可以具有从0到 e i的 e i +1值，因此 n 的因数为（ e 1 +1）•（ e 2 +1）•（
e 3 +1）•…（ e k + 1）。

由于每个 e i 必须为正，因此每个 e i +1必须至少为2。现在我们可以看到，如果 n 具有 x个 因数，则 x 可表示为
k个 整数的乘积，每个整数至少为2。反之，如果 x 可以表示为 k个 整数的乘积，每个整数至少为2，该乘积为我们提供 e i的
值，这为我们提供了一个具有 x个 因子和 k个 素数因子的正整数 n 。

因此，当且仅当 x 可表示为 k个 整数的乘积，且每个整数至少为2时，存在具有 x个 因子和 k个 素数的数字。

要对此进行测试，只需将 x 除以质数即可， 例如 ，将除以2，然后除以3，再除以5，以此类推。一旦将 x 除以 k
-1个因子并且结果大于1，则我们知道 x 可表示为 k个 整数的乘积，每个整数至少为2（最后一个可以是合成的，而不是质数，例如2•3
•3•3•35）。如果 x 在我们除以 k -1个因子之前或正好达到1时，则不存在这样的数字。

附录

进一步考虑，在对因子进行 x 检验时，不必使用质数作为候选。我们可以简单地遍历整数，测试每个候选 f 是否是 x 的因数。尝试通过首先测试
f 是否为素数来过滤它们，比简单测试 f 是否为 x 的因子要花费更多的时间。（这并不是说测试 x
的素数因子的更复杂的方法，例如使用准备好的包含许多素数的表，不会更快。）因此，下面的代码就足够了。

#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));
}