В основном проблема заключается в следующем: для набора положительных чисел найти минимальное число , которое не является делителем ни одного элемента из , т. .
Обозначим и . Рассмотрим функцию наименьшее простое число, не делящее . Легко видеть, что . А для множества , пусть наименьшее простое число , что не разделяет какой - либо элемент . У нас есть верхняя граница
Поэтому простой алгоритм перебора, который перечисляет все числа от до и проверяет, не разделяет ли он какой-либо элемент из , является полиномиальным и имеет временную сложность .
Другой способ решить эту проблему - вычислить все факторы для каждого элемента и использовать их в алгоритме перебора, чтобы проверить, является ли ответом за времени. Этот алгоритм имеет временную сложность и использует память, потому что нам не нужно вычислять и магазин факторов больше , чем . Для малых и это работает лучше.
Подробно алгоритм состоит из двух частей:
Построить множество составленное из всех факторов всех элементов , т.е.
Это можно сделать за и памяти. (Откуда это берется? Для любого элемента мы можем разложить его, используя либо пробную факторизацию со всеми числами до либо со всеми простыми числами до , в зависимости от того, что меньше; таким образом, каждый элемент из может быть учтено во времени время.)Найдите минимальное число . Этот шаг требует времени, если проверяется, можно ли выполнить за время.
У меня есть два вопроса, которые меня интересуют:
- Есть ли более быстрый алгоритм для решения проблемы?
- Для данных и , как мы можем построить множество с максимальным наименьшим общим неделителем?
источник
Ответы:
Возможно улучшить ваш второй алгоритм, используя лучшие алгоритмы для целочисленной факторизации.
Есть два алгоритма для целочисленной факторизации, которые здесь важны:
GNFS может целое число со временем выполнения .≤C O(LC[0.33,1.92])
ECM может найти факторы (если таковые имеются) со временем выполнения ; нахождение всех факторов займет раз (что относительно мало по сравнению с временем работы ECM).≤nlogC O(LnlogC[0.5,1.41]) O(logC/log(nlogC))
Здесь .Ln[α,c]=exp{c(logn)α(loglogn)1−α}
Это довольно ужасно выглядящее выражение для времени выполнения, но важным фактом является то, что это быстрее, чем методы, которые вы упомянули. В частности, асимптотически намного меньше, чем , т. намного быстрее, чем пробует все возможные факторы . Также асимптотически значительно меньше , то есть ECM гораздо быстрее , чем пытаться все возможные факторы .LC[0.33,1.92] C−−√ ≤C−−√ LnlogC[0.5,1.41] nlogC ≤nlogC
Таким образом, общее время выполнения этого метода примерно равно , и это асимптотически лучше, чем ваш Первый метод и асимптотически лучше, чем ваш второй метод. Я не знаю, возможно ли сделать еще лучше.O~(nmin(LC[0.33,1.92],LnlogC[0.5,1.41]))
источник
Наименьший общий неделитель может быть таким же большим, как N log C, но если N чисел распределены случайным образом, то наименьший общий неделитель, вероятно, будет намного меньше, вероятно, намного меньше N. Я бы построил таблицы, из которых простые числа делители которых числа.
Для каждого простого числа p у нас есть индекс который означает, что все числа до этого индекса были проверены на делимость на p, и у нас есть список всех тех чисел, на которые делятся.kp
Тогда для d = 2, 3, 4, ... мы пытаемся найти число, делимое на d, или показать, что его нет. Мы берем наибольший простой множитель p of d. Затем мы проверяем все числа, которые делятся на p, делятся ли они также на d. Если ничего не найдено, то мы проверяем дальнейшие числа с индексами> на делимость на p, обновляем и список чисел , p, и проверяем, делится ли каждое число на d.kp kp
Чтобы проверить, существует ли число, делимое на p, мы проверяем в среднем число p. Позже, если мы проверим, есть ли число, делимое на 2p, есть 50% -ый шанс, что нам нужно проверить только одно число (то, которое делится на p), и 50% -ый шанс проверить в среднем на 2p больше чисел. Найти число, делимое на 3p, вполне вероятно, быстро и так далее, и мы никогда не проверяем делимость на p больше чем N чисел, потому что есть только N чисел.
Я надеюсь, что это с проверок делимости.N2/logN
PS. Насколько большим будет результат для случайных чисел?
Предположим, у меня есть N случайных чисел. Вероятность того, что одно из N чисел делится на d, равна 1 - (1 - 1 / d) ^ N. Я предполагаю, что вероятность того, что каждое из чисел 1 ≤ d ≤ k является фактором одного из случайных чисел, рассчитывается путем умножения этих вероятностей (хорошо, это немного хитроумно, потому что эти вероятности, вероятно, не совсем независимы).
С этим допущением, при N = 1000, есть 50% -ная вероятность того, что одно из чисел 1..244 не делит ни одного числа, и одно из миллиарда, что каждое число до 507 делит одно из чисел. При N = 10000 есть 50% вероятность того, что одно из чисел 1..1726 не делит ни одного числа, а одно на миллиард, что каждое число до 2979 делит одно из чисел.
Я хотел бы предложить, что для N случайных входов размер результата немного больше, чем N / ln N; может быть что-то вроде N / ln N * (ln ln N) ^ 2. Вот почему:
Вероятность того, что по меньшей мере один из N случайных чисел делятся на случайный д составляет . Если d около N, то составляет около 1 - exp (-1) ≈ 0,6321. Это для одного делителя; шансы того, что каждое из нескольких чисел d ≈ N является делителем хотя бы одного из N чисел, достаточно малы, поэтому максимальное значение d будет значительно меньше N.1−(1−1/d)N 1−(1−1/d)N
Если d << N, то .1−(1−1/d)N≈1−exp(−N/d)
Если d ≈ N / N , то пер .1−exp(−N/d)≈1−exp(−lnN)=1−1/N
Мы добавили бы эти вероятности для примерно N / ln N значений d, но для большинства d результат будет значительно больше, поэтому самый большой d будет как-то больше, чем N / ln N, но значительно меньше, чем N.
PS. Нахождение числа, делимого на d:
Мы выбираем наибольший простой фактор p из d, а затем сначала исследуем числа, которые, как известно, делятся на p. Скажи д = кп. Тогда в среднем мы проверяем только k чисел, которые делятся на p, при проверке этого конкретного d, и мы проверяем самое большее все N значений для делимости на p в целом, для всех d, делимых на p. На самом деле, мы, скорее всего, проверяем значения меньше N для большинства простых чисел p, потому что после проверки всех значений N алгоритм, скорее всего, заканчивается. Таким образом, если результат равен R, то я ожидаю, что меньше чем N значений будет делиться на каждое простое число меньше R. Предполагая, что R ≤ N, это примерно N ^ 2 / log N проверок.
PS. Выполнение некоторых тестов
Я запускал этот алгоритм несколько раз с N = 1 000 000 случайных чисел> 0. Наименее распространенный неделитель составлял от 68 000 до 128 000, причем подавляющее большинство прогонов - от 100 000 до 120 000. Количество делений составляло от 520 до 1800 миллионов, что намного меньше (N / ln N) ^ 2; В большинстве случаев используется от 1000 до 1500 миллионов делений.
источник