Алгоритм определения набора чисел, который можно разложить на 2^p5^q

Я пытаюсь написать алгоритм, который может вернуть набор натуральных чисел, который меньше, чем экземпляр n и может быть разложен на множители как 2^p5^q. Моя математика не самая лучшая, поэтому я понятия не имею, как я могу определить, может ли число быть разложено в этой конкретной форме...

Любая помощь приветствуется:)

Источник

3 ответа

Решение

Я понятия не имею, как я могу определить, можно ли факторизовать число в этой конкретной форме

Вместо того, чтобы проверять, может ли данное число быть разложено на множители и проходить через все числа, меньшие n, почему бы просто не сгенерировать их, например

void findNumbers(int n)
{
    int p = 0;
    int power2 = 1; 
    while(power2 < n)
    {
        int q = 0;
        int power5 = 1;
        while(power5 * power2 < n)
        {
            printf("%d p = %d q = %d\n", power5 * power2, p, q);
            power5 *= 5;
            q++;
        }
        power2 *= 2;
        p++;
    }
}

Выход для n = 500:

1 p = 0 q = 0
5 p = 0 q = 1
25 p = 0 q = 2
125 p = 0 q = 3
2 p = 1 q = 0
10 p = 1 q = 1
50 p = 1 q = 2
250 p = 1 q = 3
4 p = 2 q = 0
20 p = 2 q = 1
100 p = 2 q = 2
8 p = 3 q = 0
40 p = 3 q = 1
200 p = 3 q = 2
16 p = 4 q = 0
80 p = 4 q = 1
400 p = 4 q = 2
32 p = 5 q = 0
160 p = 5 q = 1
64 p = 6 q = 0
320 p = 6 q = 1
128 p = 7 q = 0
256 p = 8 q = 0

Он просто перебирает каждую комбинацию p и q до n.

Если вы хотите исключить p = 0 и q = 0, просто начните петли с 1 и установите power2 = 2 и power5 = 5.

Источник

Используйте две очереди: q1, q2,

Начать с q1,q2 пустой.

(В следующем q.head() == 1 если q пусто, нужно только для первых итераций)

Repeat while `min{q1.head(), q2.head()} <n`:
    let x = min{q1.head(), q2.head()}
    yield x
    remove x from relevant queue
    q1.add(x*2)
    q2.add(x*5)

Идея в том, если x1 был обработан до x2тогда это значит x1<x2, и поэтому x1*2 < x2*2 а также x1*5 < x2*5 - таким образом, очереди поддерживаются в порядке, и все, что вам нужно сделать в каждой точке, это проверить, какая из очередей должна быть опрошена на каждом шаге, что довольно просто.


Обратите внимание, что таким же образом вы можете легко обрезать дубликаты, потому что числа производятся по порядку, и вам просто нужно пропустить числа, если они идентичны последнему, который был обработан.

Плюсы этого решения:

  1. Сложность этого решения линейна по количеству произведенных элементов.
  2. Произведенный список уже отсортирован, если нужно.
  3. Если тебе надо k Во-первых, это решение довольно эффективно, так как оно работает в O(k)и вы просто сломаете после производства kй элемент.
Источник

Вполне вероятно, что вам понадобится лучший алгоритм, чем "генерировать все числа, а затем проверить, что они 2^p 5^q". Но чтобы ответить на ваш вопрос, как определить, имеет ли положительное число форму 2^p 5^qРазделяешь все возможное 2с и 5s. Если что-то осталось, исходное число не имело факторизации:

while ( n % 5 == 0 ) {
    n /= 5;
}
while ( n % 2 == 0 ) {
    n /= 2;
}
return n==1;

Есть более быстрые способы проверить, является ли число 2^p, но я считаю их менее читаемыми, чем последние четыре строки.

Источник
Другие вопросы по тегам