0

Нужно найти количество делителей n-значного числа (n > 20). Как это реализовать?

IWProgrammer
  • 841
  • 1
  • 15
  • 31
  • Используя длинную арифметику. – Harry Nov 22 '16 at 13:27
  • В общем случае - никак. Особенно когда n очень велико. – Zealint Nov 22 '16 at 13:27
  • @Harry , можно алгоритм? Я смотрел длинную арифметику для деления, но она не понятна, так как делим столбиком. Но если таким образом искать количество делителей у двадцатизначного числа, то работа программы займет очень много времени – IWProgrammer Nov 22 '16 at 13:29
  • А по-другому пока что никак. Если бы можно было быстро раскладывать очень большие числа на множители, то шифрование RSA тут же приказало бы долго жить... Вы дайте хоть какие-то ограничения сверху - а то как знать, может, у вас вообще миллион цифр в числе... – Harry Nov 22 '16 at 13:30

1 Answers1

1

1 Можете изучить длинную арифметику. Например, здесь или здесь.

2 Можете использовать готовую длинную арифметику. Например, MPIR или GMP

Ну а дальше делаете перебор по всем простым числам, в надежде, что это будет работать быстро. В худшем случае это будет работать... несколько миллиардов лет.

UPD: Вот, кстати, случайное 21-значное простое число для проверки 235910232262849857961

Zealint
  • 3,958
  • А, не, в худшем случае это будет работать бесконечно долго... n>20... – Zealint Nov 22 '16 at 13:35
  • оставлю тут эти ссылки http://e-maxx.ru/algo/factorization http://e-maxx.ru/algo/bpsw – pavel Nov 22 '16 at 14:07