寻找给定对的解决方案（因子数，素数因子）
Finding solutions for a given pair (number of factors, number of prime factors)
我得到了x和k，其中x是一个数的因数个数A，k是这个数A 的质因数。给定 x 和 k，我必须找出这样的 A 是否存在。
例如：
INPUT : 4 2
OUTPUT : 1
因为 6 是一个有 4 个因数 1, 2, 3, 6 的数，其中 2 个是质数 (2, 3)。
此外，x 和 k 可以具有 1 到 109.
之间的任何值
这是我的代码：
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);
其中 isprime(x) returns 1 如果 x 是质数 否则 0.
但是在运行程序中，显示TLE错误。
谁能帮我优化这个算法，或者如果存在任何其他方法，你能给我解释一下吗？
如果您能帮助优化此算法或使用其他方法，我们将不胜感激。
您的算法非常效率低下。这里有一些想法：
- 拒绝明显失败：如果
x < 2 或 k <= 0 或 x < k 答案是 0，无需进一步测试。
- 不要混用浮点数和整数运算。使用
1000000000 而不是 pow(10, 9).
- 内部循环可以比您更早地停止：仅 运行 它而
a * a < numbers 并为每个匹配添加 2 个除数。如果 a * a == numbers. 添加另一个除数
- 如果
noOfFactors > x 或 noOfPrimes > k 也停止内循环。
程序会 运行 更快，但它仍然不是正确的方法，因为解决方案 A 可能比整数类型的范围大得多。例如 x = 1000, k = 1 对于任何素数 p 都有无限多个解 A = p999。通过枚举找到这个解决方案是不可能的。
从数学上分析问题：具有 k 个质因数的数 A 的总因数是 (e1+1)(e2+1)...(ek+1 )，其中ei是其第i个素因数的幂，即：A = Prod(piei).
为了存在一个解决方案，x 必须是至少 k 个因素的乘积。分解循环的修改版本可以确定是否可以找到至少 k 个乘积等于 x 的因子。
这是一个使用这种方法的简单程序，一旦找到 k 个因素就会完成：
#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;
}
首先你的实现效率太低
不要像这样在 for 循环中调用函数
for (long long int numbers = 1; numbers < pow(10, 9) && !stop; numbers++)
pow 将在每次迭代时不必要地调用。在循环之前将每个常量保存到变量中。但在这种情况下，只需使用 numbers < 1e9
要获得 n 的所有因子，您只需循环直到 sqrt(n)。你正在做 for (long long int a = 1; a <= numbers && !stop; a++) { if (numbers % a == 0) { 所以例如你需要 10 而不是只有 104 循环 108 ]8 循环。如果 numbers % a == 0 那么 a 和 numbers/a 都是 numbers
但这里真正的问题是你的算法有缺陷。如果你知道 A 的质因数及其指数，你就可以得到 A 的所有因数。如果 A = p1m p2n 。 .. pkp 则A将有以下因素：
- p1i 因为 i = 1..m
- p2i 因为 i = 1..n
- ...
- pki 对于 i = 1..p
- 2个质因数的因数：p1ip2j,p1ip3j,... p1ipkj, p2ip3j, p2ip4j,. .. p2ipkj,. .. pk-1ipkj
- 来自 3 个主要因素的因素...
- 来自 k 个质因数的因数
这纯粹是一个组合计数问题，即使不知道A也可以轻松完成。注意k个质因数的因子数与k-1个质因数的因子数有一定关系
设p1,p2, p3, … pk是某个正整数n的质因数。由fundamental theorem of arithmetic，n可以表示为p1 e1•p2 e2•p3 e3• ... p kek 对于一些正整数 e1, e2, e3, ... ek。此外，任何这样的正整数集合都以这种方式表示一个正整数。
n的每一个因子都可以表示为p1 f1•p2 f2•p3 f3• ... p kfk 对于某些整数 fi 其中 0 ≤ fi ≤ e i.
每个fi可以有ei+1 值从 0 到 ei ,所以n的因子个数为(e1+1)•(e2+1)•(e 3+1)• … (ek+1).
由于每个 ei 必须为正数，因此每个 e i+1 必须至少为 2。现在我们可以看到，如果 n 有 x 个因子，那么 x 可以表示为 k 个整数的乘积，每个整数至少为 2 . 相反，如果 x 可表示为 k 个整数的乘积，每个整数至少为 2，则该乘积为我们提供 e 的值i，这给了我们一个正整数 n 有 x 个因子和 k 个质因子。
因此，当且仅当x 可表示为 k 个整数的乘积，每个整数至少为 2.
为了测试这一点，只需将 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 的素数因子的方法，例如使用准备好的 table 许多素数，不会更快。）所以下面代码就够了。
#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));
}
我得到了x和k，其中x是一个数的因数个数A，k是这个数A 的质因数。给定 x 和 k，我必须找出这样的 A 是否存在。
例如：
INPUT : 4 2
OUTPUT : 1
因为 6 是一个有 4 个因数 1, 2, 3, 6 的数，其中 2 个是质数 (2, 3)。
此外，x 和 k 可以具有 1 到 109.
这是我的代码：
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);
其中 isprime(x) returns 1 如果 x 是质数 否则 0.
但是在运行程序中，显示TLE错误。 谁能帮我优化这个算法，或者如果存在任何其他方法，你能给我解释一下吗？ 如果您能帮助优化此算法或使用其他方法，我们将不胜感激。
您的算法非常效率低下。这里有一些想法：
- 拒绝明显失败：如果
x < 2或k <= 0或x < k答案是0，无需进一步测试。 - 不要混用浮点数和整数运算。使用
1000000000而不是pow(10, 9). - 内部循环可以比您更早地停止：仅 运行 它而
a * a < numbers并为每个匹配添加 2 个除数。如果a * a == numbers. 添加另一个除数
- 如果
noOfFactors > x或noOfPrimes > k也停止内循环。
程序会 运行 更快，但它仍然不是正确的方法，因为解决方案 A 可能比整数类型的范围大得多。例如 x = 1000, k = 1 对于任何素数 p 都有无限多个解 A = p999。通过枚举找到这个解决方案是不可能的。
从数学上分析问题：具有 k 个质因数的数 A 的总因数是 (e1+1)(e2+1)...(ek+1 )，其中ei是其第i个素因数的幂，即：A = Prod(piei).
为了存在一个解决方案，x 必须是至少 k 个因素的乘积。分解循环的修改版本可以确定是否可以找到至少 k 个乘积等于 x 的因子。
这是一个使用这种方法的简单程序，一旦找到 k 个因素就会完成：
#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;
}
首先你的实现效率太低
不要像这样在 for 循环中调用函数
for (long long int numbers = 1; numbers < pow(10, 9) && !stop; numbers++)pow将在每次迭代时不必要地调用。在循环之前将每个常量保存到变量中。但在这种情况下，只需使用numbers < 1e9要获得
n的所有因子，您只需循环直到sqrt(n)。你正在做for (long long int a = 1; a <= numbers && !stop; a++) { if (numbers % a == 0) {所以例如你需要 10 而不是只有 104 循环 108 ]8 循环。如果numbers % a == 0那么a和numbers/a都是numbers 的因子
但这里真正的问题是你的算法有缺陷。如果你知道 A 的质因数及其指数，你就可以得到 A 的所有因数。如果 A = p1m p2n 。 .. pkp 则A将有以下因素：
- p1i 因为 i = 1..m
- p2i 因为 i = 1..n
- ...
- pki 对于 i = 1..p
- 2个质因数的因数：p1ip2j,p1ip3j,... p1ipkj, p2ip3j, p2ip4j,. .. p2ipkj,. .. pk-1ipkj
- 来自 3 个主要因素的因素...
- 来自 k 个质因数的因数
这纯粹是一个组合计数问题，即使不知道A也可以轻松完成。注意k个质因数的因子数与k-1个质因数的因子数有一定关系
设p1,p2, p3, … pk是某个正整数n的质因数。由fundamental theorem of arithmetic，n可以表示为p1 e1•p2 e2•p3 e3• ... p kek 对于一些正整数 e1, e2, e3, ... ek。此外，任何这样的正整数集合都以这种方式表示一个正整数。
n的每一个因子都可以表示为p1 f1•p2 f2•p3 f3• ... p kfk 对于某些整数 fi 其中 0 ≤ fi ≤ e i.
每个fi可以有ei+1 值从 0 到 ei ,所以n的因子个数为(e1+1)•(e2+1)•(e 3+1)• … (ek+1).
由于每个 ei 必须为正数，因此每个 e i+1 必须至少为 2。现在我们可以看到，如果 n 有 x 个因子，那么 x 可以表示为 k 个整数的乘积，每个整数至少为 2 . 相反，如果 x 可表示为 k 个整数的乘积，每个整数至少为 2，则该乘积为我们提供 e 的值i，这给了我们一个正整数 n 有 x 个因子和 k 个质因子。
因此，当且仅当x 可表示为 k 个整数的乘积，每个整数至少为 2.
为了测试这一点，只需将 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 的素数因子的方法，例如使用准备好的 table 许多素数，不会更快。）所以下面代码就够了。
#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));
}