查找给定对的解决方案（因子数量，主要因子数量） [英] Finding solutions for a given pair (number of factors, number of prime factors)

问题描述

我得到了 x 和 k ，其中 x 是数量 A 的因数，而 k 是数量<$ c的素数$ c> A 。给定 x 和 k ，我必须找出是否这样的 A 存在。

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.

例如：

INPUT : 4 2 
OUTPUT : 1

由于6是一个具有4个因子1、2的数字3，6，其中2是质数（2，3）。
还假定 x 和 k 可以具有1到10 ^{9之间的任何值}。

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⁹.

这是我的代码：

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

其中为素数（x）如果x是质数，则返回1，否则返回0。

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

但是在运行程序时，它显示TLE错误。
谁能帮助我优化此算法，或者如果存在其他方法，您可以向我解释一下吗？
对于优化此算法或使用其他方法的任何帮助，将不胜感激。

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.

推荐答案

让 p ₁ ， p ₂ ， p ₃ ，… p _k 是某些正整数 n 的主要因子。通过算术基础定理， n 可以表示为 p ₁ ^{e ₁} • p ₂ ^{e ₂} • p ₃ ^{e ₃} •… p _k ^{e _k} 表示某些正整数 e ₁ ， e ₂ ， e ₃ ，… e _{k 。此外，任何这样的一组正整数都以这种方式表示一个正整数。}

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.

每个 n 因子都可以表示为 p ₁ ^{f ₁} • p ₂ ^{f ₂} • p ₃ ^{f ₃} •… p _k ^{f _k} 用于某些整数 f _i ，其中0≤ f _i ≤ e _i 。

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.

每个 f _i 可以具有 e _{从0到 e i 的 i} +1值，因此 n 是（ e ₁ +1）•（ e ₂ +1）•（ e ₃ +1）•…（ e _k +1）。

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).

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

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.

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

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.

要测试这一点，只需除以 x 用质数 eg 进行尽可能多的除以2，然后除以3，再除以5，依此类推。一旦将 x 除以 k −1个因子，并且结果大于1，那么我们知道 x 可表示为 k 每个整数至少为2（最后一个整数可能是合成的而不是质数，例如2•3•3•3•35）。如果 x 之前等于1或等于我们将其除以 k -1的因子，则该数字不存在。

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.

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

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

这篇关于查找给定对的解决方案（因子数量，主要因子数量）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！