Мне дан список целых чисел (до 1000), которые умножаются на заданное целое число n.
Мне нужно найти наибольшую степень среди всех делителей целого числа n.
Например: 4,7,8 умножаем на 224, и тогда максимальная степень будет 5, так как 224 = 2 ^ 2 * 7 * 2 ^ 3 = 2 ^ 5 * 7.
Проблема в том, что 1000 целых чисел могут достигать 2 ^ 64, следовательно, n очень велико.
Какой отличный алгоритм для решения этой проблемы?
Трудный. Сначала я бы начал проверять маленькие простые числа (в вашем примере: 4, 7, 8. У произведения есть множитель 2 ^ 5. Вы делите на степени двойки, оставляя 1, 7, 1. Затем вы делаете то же самое для 3 , 5, 7 и т. Д. До X).
Теперь вам нужно найти большее простое число p> X, которое является большей степенью, чем наибольшее число, которое вы нашли. Тратить много времени на поиск основных факторов, которые встречаются только один раз, кажется расточительным. Вам нужны простые числа, которые являются множителями нескольких чисел. Вычислите НОД каждой пары чисел и посмотрите на простые множители этих чисел. Есть много деталей, которые нужно проработать, поэтому я начал со «сложного».
В худшем случае вы не можете легко найти какое-либо простое число, которое встречается дважды, поэтому вам нужно проверить, содержит ли каждое из чисел квадрат простого числа в качестве множителя.
В качестве примера: вы проверили множители до 1000 и обнаружили, что наибольшая степень простого числа равна 83 ^ 3. Итак, теперь вам нужно найти большее простое число в четвертой степени или показать, что его нет. Вычислите попарные НОД (наибольший общий делитель). Большое простое число может быть делителем нескольких этих НОД, полученных от четырех разных чисел, или p может быть множителем трех НОД, с p ^ 2 множителем одного числа и т. Д.
Чтобы прояснить принцип: скажем, у вас есть два ОГРОМНЫХ числа x и y, и вы хотите знать, какое из них является наибольшей степенью простого числа, которое делит xy. Вы можете разложить на множители x и y и перейти оттуда. Если они оба являются простыми числами или произведением двух больших простых чисел, скажем, x = p или pq, а y = r или rs, это займет много времени.
Теперь вычислите НОД x и y. Если наибольший общий делитель равен z> 1, то z является делителем x и y, поэтому z ^ 2 является делителем xy. Если наибольший общий делитель равен 1, то x и y не имеют общего делителя. Поскольку нам не нужны неквадратные множители, мы ищем квадраты и множители более высокого порядка. Для этого вам нужно всего лишь разделить на множители до x ^ (1/3) или y ^ (1/3).
for(в частности, частьi=i+2) проверяет каждое нечетное число до квадратного корня из числа. Это примерно 1 миллиард делений, когда входное число состоит из 18 цифр. На это уходит много времени. - person user3386109 schedule 30.10.2016