Доброго времени суток!
Окончательно запутался с этим методом и прошу помощи у более опытных и знающих членов сообщества.
Допустим есть число до 10¹⁸, требуется его факторизовать.
Очевидно, что делители до 10⁶ легко перебираются в лоб. Остальные делители будем, допустим, искать методом факторизации Ферма. Какова будет сложность в худшем случае?
2 года назад в тренировке 2011-2012 Waterloo Local Contest, 19 June, 2011 я сдал задачу на факторизацию с 10⁶ итерациями и с тех пор поверил, что этот метод фактически работает за кубический корень для чисел до 10¹⁸.
Однако теперь я внезапно наткнулся на то, что число 100000007700000049 = 1000000007 * 100000007 совсем не хочет раскладываться с таким количеством шагов. Причиной заблуждения, что тот код был верный оказались предельно слабые тесты (в тестах было лишь на 2 числа больше, чем в примерах входных данных)
Теперь хочется узнать — это неверное понимание работы метода или его неверное применение?
Пример кода можно найти на e-maxx