число делителей числа, которые не меньше другого числа

Существует ли какой-либо эффективный способ найти число делителей числа (скажем, n), которое не меньше другого числа (скажем, m). n может быть до 10^12. я думал об алгоритме сита , а затем найти число делителей. мой метод проверяет все числа от m до квадратного корня из n. Но я думаю, что есть другой способ(эффективный) сделать это .

3 3
performance algorithm prime-factoring

3 ответа:

Ниже приведен пример программы, которая вычисляет число делителей n, которые больше m. код largeDivs() выполняется за время O (c), если есть c делителей. largeDivs() также начинается с представления n как факторизованного числа, причем nset представляет собой список пар вида (p_i, k_i), таких что n = произведение{p_i**k_i для i в 1..ч}. Некоторые выходные данные примера показаны после программы. Процедура check() используется для демонстрации того, что функция largeDivs() дает правильные результаты. проверка() занимает долгое время для меньших значений m. 

def largeDivs(n, nset, m):
    p, k = nset[-1]
    dd = 0
    if len(nset) > 1:
        nn, mm = n / p**k, m
        for i in range(k+1):
            dd += largeDivs(nn, nset[:-1], mm)
            mm = (mm + p-1)/p
    else:
        c, v = k+1, 1
        while v<m and c>0:
            c, v = c-1, v*p
        return c
    return dd

def check (n,m,s):
    if m<1:
        return s
    c = 0
    for i in range(m,n+1):
        if (n%i)==0:
            c += 1
    return c


tset = [(2,3),(3,2),(11,1),(17,1),(23,2)]
n = s = 1
for i in tset:
    s *= 1+i[1]
    n *= i[0]**i[1]
print 'n=',n, '  s=',s
m=0
for i in range(8):
    print 'm:', m, '\t', largeDivs(n, tset, m), '  Check:',check(n,m,s)
    m = 10*m + 5

Пример вывода: 

n= 7122456   s= 144
m: 0    144   Check: 144
m: 5    140   Check: 140
m: 55   124   Check: 124
m: 555  95   Check: 95
m: 5555     61   Check: 61
m: 55555    28   Check: 28
m: 555555   9   Check: 9
m: 5555555  1   Check: 1
2

Легко найти делители числа, если вы знаете простые множители; просто возьмите все возможные комбинации кратностей всех факторов.

Для n столь малого, как 10^12, пробное деление должно быть достаточно быстрым методом факторизации, поскольку вам нужно только проверить потенциальные факторы до 10^6.

Edit: добавить обсуждение "всех возможных комбинаций" и факторинга путем пробного деления.

Рассмотрим число 24505 = 5 * 13 * 13 * 29. Перечислять его делители, принимают все возможные комбинации кратностей всех факторов: 

5^0 * 13^0 * 29^0 = 1
5^0 * 13^0 * 29^1 = 29
5^0 * 13^1 * 29^0 = 13
5^0 * 13^1 * 29^1 = 377
5^0 * 13^2 * 29^0 = 169
5^0 * 13^2 * 29^1 = 4901
5^1 * 13^0 * 29^0 = 5
5^1 * 13^0 * 29^1 = 145
5^1 * 13^1 * 29^0 = 65
5^1 * 13^1 * 29^1 = 1885
5^1 * 13^2 * 29^0 = 845
5^1 * 13^2 * 29^1 = 24505

Также нетрудно разложить число на множители путем пробного деления. Вот алгоритм, который вы можете перевести на свой любимый язык; он достаточно быстр для чисел до 10^12: 

function factors(n)
    f = 2
    while f * f <= n
        if n % f == 0
            output f
            n = n / f
        else
            f = f + 1
    output n
Давайте посмотрим на факторизацию 24505. Первоначально f равно 2, но 24505% 2 = 1, поэтому f увеличивается до 3. Тогда f = 3 и f = 4 также не делятся n , но 24505% 5 = 0, поэтому 5-это коэффициент 24505, а n уменьшается до 24505 / 5 = 4901. Теперь f = 5 остается неизменным, но он не может разделить n, аналогично 6, 7, 8, 9, 10, 11 и 12, но, наконец, 4901 % 13 = 0, поэтому 13-это коэффициент 4901 (а также 24505), а n сводится к 4901 / 13 = 377. В этот момент f = 13 остается неизменным, и 13 снова является делителем, на этот раз уменьшенным n = 377, поэтому выводится еще один фактор 13 и n является сократилось до 29. В этой точке 13 * 13 = 169 больше 29, поэтому цикл while завершается, и выводится конечный коэффициент 29; это работает, потому что если n=pq, то один из p или q должен быть меньше квадратного корня n (за исключением случая, когда p и q являются равным и N является совершенным квадратом), а так как мы уже сделали пробное деление на все P и Q меньше квадратного корня из 29, то оно должно быть простым, и таким образом последний фактор. Итак, мы видим, что 24505 = 5 * 13 * 13 * 29.

Я обсуждаю эти типы алгоритмов в своем эссе Программирование с простыми числами .

3

Это зависит от приложения, но если производительность такая проблема, я бы использовал предварительно сгенерированную хэш-таблицу. Очевидно, что 10^12 записей может быть нецелесообразно (или, по крайней мере, нежелательно) хранить в памяти, поэтому я бы сделал тесты деления до kth простое число, генерирующее записи хэш-таблицы только для чисел, не делящихся на эти первые k простые числа.

Например, хотя это грубо написано и непроверено, это должно дать вам идею: 

int   number   = 23456789;
int   primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 0};
int   pfactors = 0;
int*  prime = primes;
float temp;

// check until we reach the end of the array (0)
while (prime)
{
    // divide by prime and check if result is integer
    temp = (float)number/*prime;
    if (temp == floor(temp))
    {
        // if so, increment count of prime factors and loop (same prime again!)
        pfactors++;
        number = (int)temp;
    }
    else
    {
        // else try the next prime
        prime++;
    }
}

// finally, rely on hash table magic
pfactors += pregenerated_hash[number];
0