Тема: Deliteli
Mojno li za O(Koli4est4o deliteli 4isla n) naiti vse deliteli 4isla n? ili Za skolko mojno naiti?))))))))
Re: Deliteli
Да, конечно можно. Факторизуем N:
N = a1^p1 ... ak^pk
тогда любой делитель имеет вид:
a1^i1 ... ak^ik,
где 0<=ij<=p1
Ну и собственно, все такие наборы чисел (i1...ik) можно перебрать рекурсивно, и за O от их количества.
Re: Deliteli
Можно ровно за O(sqrt(N)).
Просто перебираем все делители до корня, допустим это I,тогда N / I это тоже нейкий делитель,что бы не было повторов делителей просто припишем условие (I < N / I) тогда N / I тоже делитель.
Re: Deliteli
Ну да. Но бывают задачи, когда нужно именно за O(кол-ва делителей), т.е. ограничения специально подобраны.
Re: Deliteli
Ну тогда нужно еще найти факторизацию. А без разных быстрых методов она как раз работает за O(sqrtN).
Re: Deliteli
Я вот это хотел пометить. Факторизация занимает такое же время,а что бы писать быстрые алгоритмы нужно кучу времени.
7 2010-03-19 02:50:32 Отредактировано aropan (2010-03-19 02:51:37)
Re: Deliteli
Факторизовать можно быстрее. Найти все простые числа до корня, тем же решетом Эратосфена, и перебирать не все числа до корня, а только их.
Хотя построение решета займет тоже самое время, но это будет предпроцесс, так что если надо находить для множества чисел, то это будет выгодно.