Let p 1 , p 2 , p 3 ,… p k - главные факторы некоторого натурального числа n . По основной теореме арифметики c, n можно представить в виде p 1 e 1 • р 2 е 2 • p 3 e 3 •… p k e k для некоторых натуральных чисел e 1 , e 2 , e 3 ,… e k . Кроме того, любой такой набор таких положительных целых чисел представляет собой одно положительное целое число таким образом.
Каждый фактор n может быть представлен как p 1 * * е одна тысяча девяносто шесть * ** 1098 одна тысяча девяносто семь * 1 • р 2 * +1106 * е 2 • p 3 f 3 •… p k f k для некоторых целых чисел f i , где 0 ≤ f i ≤ e i .
Каждый f i может иметь e i + 1 значения от 0 до e i , поэтому число факторов n равно ( е * ** одна тысяча сто семьдесят шесть 1177 * 1 + 1) • ( е 2 + 1) • ( е 3 * +1186 * +1) •… ( e k + 1).
с каждого e i должно быть положительным, каждое e i + 1 должно быть не менее 2. Теперь мы можем видеть что, если n имеет x множителей, то x выражается как произведение целых чисел k каждое по крайней мере на 2. И наоборот, если x выражается как произведение k целых чисел, каждое из которых не менее 2, этот продукт дает нам значения для e i , что дает нам положительное целое число n , которое имеет x факторов и k простых факторов.
Следовательно, число с x множителей и k простых множителей существует тогда и только тогда, когда x выражается как произведение k целых чисел, каждое по крайней мере на 2.
Чтобы проверить это, просто разделите x на простые числа, например, , разделите на 2 столько раз, сколько это возможно, без остатка, затем на 3, затем на 5 и т. Д. на. Как только x было разделено на k -1 факторов и результат больше 1, мы знаем, что x выражается как произведение k целых числа, по крайней мере, 2 (последний может быть составным, а не простым числом, таким как 2 • 3 • 3 • 3 • 35). Если x достигает 1 до или просто так, как мы разделили его на k -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));
}