Подсчет делителей целых чисел без их перечисления (или оценки, если это невозможно)?

Можно ли подсчитать делители целое число без проверки каждого из них до sqrt(n)? Если нет, существует ли хотя бы один способ: оценка или приблизительно Сколько их делителей?Подсчет делителей целых чисел без их перечисления (или оценки, если это невозможно)?

Например, 28 имеет шесть делителей (1, 2, 4, 7, 14, 28). 15 имеет четыре (1, 3, 5, 15). Я хочу, скажем, выяснить, сколько дивизоров имеет 242134575355654335549798955848371716626563756785, без учета всего этого (или, по крайней мере, сделать предположение и взять его оттуда).

источник

2015-11-15 JesseTG

Можете ли вы также привести несколько примеров? –

[Целочисленные алгоритмы факторизации] (https://en.wikipedia.org/wiki/Category:Integer_factorization_algorithms) –

Я голосую, чтобы закрыть этот вопрос как вне темы, потому что речь идет не о программировании, а о математике. –

Если простые множители числа, как известно

N = p1^e1 * p2^e2 * ... * pn^en

количество делителей (e1+1)*(e2+1)* ... *(en+1)

Например 242134575355654335549798955848371716626563756785 = 5 * 48426915071130867109959791169674343325312751357 имеет 4 делителей

номер один выше 242134575355654335549798955848371716626563756786 = 2 * 101203 * 757790982862309619 * 1578643235504300177689649 имеет 16 делителей.

Доступны алгоритмы, которые находят первую факторизацию числа намного быстрее, чем пробное деление до sqrt(n). Для больших чисел это займет еще некоторое время ...

источник

2015-11-15 07:22:47 Henry

Но, опять же, дело в том, как получить первичную факторизацию из первых рук! –

Если есть немало мелких факторов, простая факторизация будет идти быстро. (Каждый найденный вами делитель сокращает размер проблемы). Это цифры, которые, как оказалось, являются первичными, или продуктом больших простых чисел, которые занимают много времени. Ваш ответ подразумевает, что нет никакого трюка для подсчета делителей, не найдя их. Вы уверены, что нет известного алгоритма? И если да, знаете ли вы, было ли доказано, что их нет? Я имею в виду, я не думаю, что есть один, но я не теоретик числа, и есть множество вещей, которые я не знаю. : P –

@PeterCordes, конечно, нельзя быть уверенным, что нет трюка, и я не знаю доказательств того, что никто не существует. – Henry

-1

Существует способ факторизации числа быстрее, чем sqrt (N), но если условие n < = 10^7 истинно. В способе используется сито Eratosthenes. Here - хорошее объяснение, о котором я также узнал. Вы можете попросить меня дать разъяснения.

источник

2015-11-15 08:39:15

На самом деле это не так, есть способы ускорить факторизацию. – harold

Вы говорите, что есть способы сделать это быстрее, чем logN или быстрее, чем sqrt (n), и условие n <= 10^7 не должно быть истинным? –

Быстрее, чем sqrt (N), условие n <= 10^7 не имеет большого смысла, что заставило бы даже самый худший возможный алгоритм стать постоянным. – harold

Подсчет делителей целых чисел без их перечисления (или оценки, если это невозможно)?

ответ

Смежные вопросы