Разложить целые числа больше 100 цифр
X а также Y целые числа больше 100 цифр. Найти целое число P который находится в пределах диапазона [X, Y[и это гарантирует «наилучшее» простое разложение (то есть разложение с наибольшим уникальный главные факторы).
Что я сделал, так это просто проверил первичность и разложил каждое число в диапазоне и нашел число, соответствующее правилу. Есть ли другой способ сделать это?
Редактировать:
В приведенном выше примере 123456 разлагается на
2^6 * 3^1 * 643^1, это 2 * 2 * 2 * 2 * 2 * 2 * 3 * 643 но только 3 уникальных фактора.
В то время как ответ, 123690, раскладывается на 6 уникальных факторов
2^1 * 3^1 * 5^1 * 7^1 * 19^1 * 31^1,
Решение
Ответ на вопросы о перечислении простых чисел всегда состоит в том, чтобы найти способ решить проблему с помощью сита; в вашем случае вы ищете «простые числа» с большим количеством факторов, но принцип все еще применяется.
Ключ к этому вопросу заключается в том, что для большинства чисел большинство факторов невелики. Таким образом, я предлагаю установить сито для диапазона от X до Y, содержащее целые числа, инициализированные нулями. Затем рассмотрите все простые числа меньше некоторого предела, настолько большие, насколько это удобно, но, очевидно, намного меньше, чем X. Для каждого простого числа добавьте 1 к каждому элементу сита, кратному простому числу. После просеивания со всеми простыми точками расположение сита с наибольшим числом соответствует числу между X и Y, которое имеет наиболее различимые простые факторы.
Давайте рассмотрим пример: возьмите диапазон от 100 до 125 и просейте с простыми числами 2, 3, 5 и 7. Вы получите что-то вроде этого:
100 2 5
101 (101)
102 2 3 (17)
103 (103)
104 2 (13)
105 3 5 7
106 2 (53)
107 (107)
108 2 3
109 (109)
110 2 5 (11)
111 3 (37)
112 2 7
113 (113)
114 2 3 (19)
115 5 (23)
116 2 (29)
117 3 (13)
118 2 (59)
119 7 (17)
120 2 3 5
121 (11)
122 2 (61)
123 3 (41)
124 2 (31)
125 5
Таким образом, победителями являются 105 и 120, каждый из которых имеет три основных фактора; вам придется решить для себя, что делать с галстуками. Обратите внимание, что некоторые факторы пропущены: 11 делит 110 и 121, 13 делит 104 и 117, 17 делит 102 и 119, 19 делит 114, 23 делит 115, 29 делит 116, 31 делит 124, 37 делит 111, 41 делит 123, 53 делит 106, 59 делит 118, 61 делит 122 и, конечно, 101, 103, 107, 109 и 113 являются простыми. Это означает, что 102, 110 и 114 также связаны с лидерством, каждый из которых имеет три основных фактора. Таким образом, этот алгоритм не идеален, но для X и Y в диапазоне сотен цифр, и при условии, что вы просеиваете простые числа до миллиона или десяти миллионов, вряд ли вы существенно упустите ответ.
Хороший вопрос. Ищите это скоро в мой блог.
Другие решения
Возьмите список всех простых чисел по порядку (2,3,5,7 …) и начните их умножать (2 * 3 * 5 * …), пока не получите число> = X. Назовите это число P ‘. Если это <= Y, все готово, P = P ‘. Если нет, начните вычислять P ‘/ 2, P’ / 3, P ‘/ 5 и т. Д., Ища число [X, Y]. Если вы не нашли его и попали на номер < X, попробуйте умножить затем на простое число до P ‘и продолжить. Если это по-прежнему не удается, то диапазон [X, Y] довольно мал, поэтому вернитесь к методу факторизации всех чисел в этом диапазоне.
Для небольшого диапазона (Y-X мал), выделите массив размера Y-X + 1, обнулите его, затем для всех простых чисел <= Y-X, добавьте единицу к элементам массива, соответствующим кратным простого числа (простой набор). Затем найдите элемент с наибольшим количеством. Если это общее n таково, что (Y-X)N > = X, тогда это ответ. Если нет, продолжайте просеивать простые числа больше Y-X, пока не дойдете до некоторого простого числа p, такого что pN > X для некоторого n в таблице …
Один из двух вышеуказанных методов должен работать, в зависимости от того, насколько велик диапазон …