<Алгоритмы> Проблема делителей

Question

Учитывая количество делителей, мы должны найти первое число треугольника.

Число треугольника такое же, как сумма натуральных чисел.

У меня былопринял метод взятия простых чисел, начиная с 2, и перестановки их так, чтобы сгенерированное число совпадало с номером треугольника.

Например, предположим, что нам дано 5 делителей.Я беру простые числа, начиная с 2 (2,3,5) и N=p1^a1*p2*a2*p3^a3.Количество делителей (a1+1)(a2+1)...., здесь 2,3,5 может принимать степени и перестановки.Тогда n^2+n=2k (k - это значение, полученное из перестановки).Я проверяю значение, чтобы быть Integer.

Я не нашел ни одного эффективного алгоритма, кроме этого, есть ли у кого-нибудь более оптимальный?

Answer 1

Вы можете использовать обратный подход. Так как номер n-го треугольника можно найти как (n ^ 2 + n) / 2, вы можете просто итерировать n и для каждого числа считать его делители. Некоторые оптимизации:

• (n ^ 2 + n) / 2 = n (n + 1) / 2. n и n + 1 не имеют общих делителей (кроме 1), и только один из них является четным. Следовательно, число делителей является либо умноженным числом делителей n / 2 и n + 1, либо умноженным числом делителей n и (n + 1) /2.
• количество делителей можно найти по формуле, которую вы упомянули, поэтому вам нужен только список простых чисел (например, получите здесь )

Этот подход кажется немного более простым и оптимальным. Более того, это гарантирует, что вы найдете первый номер треугольника.