Сообщение Re[5]: задачки с хедхантера от 13.10.2016 18:06
Изменено 13.10.2016 18:08 cures
Здравствуйте, Lexey, Вы писали:
L>Не факт. И так очень шустро работает.
Вот тут чуть шустрее, хотя я всего лишь сделал перебиралку до корня в факторизации. Ну и переставил замер времени до первого вывода, ибо мерять время вывода — баловство. Если что, можно там же и меряться, мы же — профессионалы
C>>Ну и факторизация каждого числа — это жесть, для таких маленьких чисел тупо составляется решето на 2.4М интов, в котором каждому числу сопоставляется один из его простых множителей, тут наверное будет самый толстый выигрыш.
L>Идея хорошая. Но, не принципиально, ибо факторизация все равно будет линейной (только константа уменьшается), а мороки с реализацией больше.
Факторизация будет (практически) линейной по максимальному числу, а при независимой факторизации она требует примерно количество чисел в диапазоне, помноженной на корень из большего числа, то есть в худшем случае — большее число в степени 1.5.
L>Перебираются простые до корня из N. Корень из конкретного числа в данной задаче не сильно меньше будет.
Нет, перебираются до самого N. Вот если бы Вы заменили if (p > n) break; на if (p > n / p) break; то перебирались бы до корня.
L>Не факт. И так очень шустро работает.
Вот тут чуть шустрее, хотя я всего лишь сделал перебиралку до корня в факторизации. Ну и переставил замер времени до первого вывода, ибо мерять время вывода — баловство. Если что, можно там же и меряться, мы же — профессионалы
C>>Ну и факторизация каждого числа — это жесть, для таких маленьких чисел тупо составляется решето на 2.4М интов, в котором каждому числу сопоставляется один из его простых множителей, тут наверное будет самый толстый выигрыш.
L>Идея хорошая. Но, не принципиально, ибо факторизация все равно будет линейной (только константа уменьшается), а мороки с реализацией больше.
Факторизация будет (практически) линейной по максимальному числу, а при независимой факторизации она требует примерно количество чисел в диапазоне, помноженной на корень из большего числа, то есть в худшем случае — большее число в степени 1.5.
L>Перебираются простые до корня из N. Корень из конкретного числа в данной задаче не сильно меньше будет.
Нет, перебираются до самого N. Вот если бы Вы заменили if (p > n) break; на if (p > n / p) break; то перебирались бы до корня.
Re[5]: задачки с хедхантера
Здравствуйте, Lexey, Вы писали:
L>Не факт. И так очень шустро работает.
Вот тут чуть шустрее, хотя я всего лишь сделал перебиралку до корня в факторизации. Ну и переставил замер времени до первого вывода, ибо мерять время вывода — баловство. Если что, можно там же и меряться, мы же — профессионалы
C>>Ну и факторизация каждого числа — это жесть, для таких маленьких чисел тупо составляется решето на 2.4М интов, в котором каждому числу сопоставляется один из его простых множителей, тут наверное будет самый толстый выигрыш.
L>Идея хорошая. Но, не принципиально, ибо факторизация все равно будет линейной (только константа уменьшается), а мороки с реализацией больше.
Факторизация будет (практически) линейной по максимальному числу, а при независимой факторизации она требует примерно количество чисел в диапазоне, помноженной на корень из большего числа, то есть в худшем случае — большее число в степени 1.5.
L>Перебираются простые до корня из N. Корень из конкретного числа в данной задаче не сильно меньше будет.
Нет, перебираются до самого N. Вот если бы Вы заменили if (p > n) break; на if (p > n / p) break; то перебирались бы до корня.
Update: понял, перебираются до корня из максимального числа, но достаточно часто будут иметься маленькие множители, что сократит перебор. Можете попробовать.
L>Не факт. И так очень шустро работает.
Вот тут чуть шустрее, хотя я всего лишь сделал перебиралку до корня в факторизации. Ну и переставил замер времени до первого вывода, ибо мерять время вывода — баловство. Если что, можно там же и меряться, мы же — профессионалы
C>>Ну и факторизация каждого числа — это жесть, для таких маленьких чисел тупо составляется решето на 2.4М интов, в котором каждому числу сопоставляется один из его простых множителей, тут наверное будет самый толстый выигрыш.
L>Идея хорошая. Но, не принципиально, ибо факторизация все равно будет линейной (только константа уменьшается), а мороки с реализацией больше.
Факторизация будет (практически) линейной по максимальному числу, а при независимой факторизации она требует примерно количество чисел в диапазоне, помноженной на корень из большего числа, то есть в худшем случае — большее число в степени 1.5.
L>Перебираются простые до корня из N. Корень из конкретного числа в данной задаче не сильно меньше будет.
Нет, перебираются до самого N. Вот если бы Вы заменили if (p > n) break; на if (p > n / p) break; то перебирались бы до корня.
Update: понял, перебираются до корня из максимального числа, но достаточно часто будут иметься маленькие множители, что сократит перебор. Можете попробовать.