D
Quixiote
вектор будет быстрее массива?
Вектор и есть массив
Size: a a a
2020 July 19
🎄T
Quixiote
вектор будет быстрее массива?
Нет, но ты знаешь сколько у кого делителей?
Q
Нет, но ты знаешь сколько у кого делителей?
не знаю. Я заранее отвел 8. До 10^5 это достаточно. но видимо еще нужно добавить число простых в разложении. Иначе как мне потом их все выбирать. Либо каждый раз по 8 штук смотреть, что глупо.
AF
8 это я полагаю
2*3*5... > 100000?
2*3*5... > 100000?
Q
8 это я полагаю
2*3*5... > 100000?
2*3*5... > 100000?
да
В
Quixiote
Ребята, мне надо найти разложения на простые множители всех чисел до n=10^5, желательно побыстрее. Вопрос:
1) Правильно ли я понимаю, что лучше делать по типу решета эратосфена: идти по массиву чисел с простым шагом р и делить каждое по максимуму на это р?
2) Как лучше хранить найденные факторизации? Я собираюсь в виде массива длиной n из структур вида
Это нормально? Или лучше как-то по другому?
1) Правильно ли я понимаю, что лучше делать по типу решета эратосфена: идти по массиву чисел с простым шагом р и делить каждое по максимуму на это р?
2) Как лучше хранить найденные факторизации? Я собираюсь в виде массива длиной n из структур вида
struct prime_factors {
int primes[8];
int exp[8];
};Это нормально? Или лучше как-то по другому?
template<size_t N, size_t I>
struct is_prime : boost::mpl::if_c<(N%I == 0), boost::mpl::false_, is_prime<N, I - 1>>::type {};
template<size_t N>
struct is_prime<N, 1> : boost::mpl::true_ {};
AF
template<size_t N, size_t I>
struct is_prime : boost::mpl::if_c<(N%I == 0), boost::mpl::false_, is_prime<N, I - 1>>::type {};
template<size_t N>
struct is_prime<N, 1> : boost::mpl::true_ {};
Оу фак
AF
Nsqrt(n) на этапе компиляции
Q
template<size_t N, size_t I>
struct is_prime : boost::mpl::if_c<(N%I == 0), boost::mpl::false_, is_prime<N, I - 1>>::type {};
template<size_t N>
struct is_prime<N, 1> : boost::mpl::true_ {};
блин, нихера не понимаю :)) boost - это сторонняя либа?
SM
Quixiote
Ребята, мне надо найти разложения на простые множители всех чисел до n=10^5, желательно побыстрее. Вопрос:
1) Правильно ли я понимаю, что лучше делать по типу решета эратосфена: идти по массиву чисел с простым шагом р и делить каждое по максимуму на это р?
2) Как лучше хранить найденные факторизации? Я собираюсь в виде массива длиной n из структур вида
Это нормально? Или лучше как-то по другому?
1) Правильно ли я понимаю, что лучше делать по типу решета эратосфена: идти по массиву чисел с простым шагом р и делить каждое по максимуму на это р?
2) Как лучше хранить найденные факторизации? Я собираюсь в виде массива длиной n из структур вида
struct prime_factors {
int primes[8];
int exp[8];
};Это нормально? Или лучше как-то по другому?
нужно хранить минимальный простой делитель для каждого из чисел...по ним возмжно будет восстановить общий ответ....время работы алгоритма O (n)
Q
нужно хранить минимальный простой делитель для каждого из чисел...по ним возмжно будет восстановить общий ответ....время работы алгоритма O (n)
Мне нужно, чтобы потом доступ был максимально быстрым.
В
Quixiote
блин, нихера не понимаю :)) boost - это сторонняя либа?
да но можно стл заменить, там где if_c будет std::conditional
SM
Quixiote
Мне нужно, чтобы потом доступ был максимально быстрым.
O(30) максимум наверное
SM
решето используй
AF
Quixiote
Мне нужно, чтобы потом доступ был максимально быстрым.
Там восстановление за линию если хранить только одно число
🎄T
Там восстановление за линию если хранить только одно число
За логарифм же если не меньше
AF
Ну смысле за кол-во делителей
SM
Там восстановление за линию если хранить только одно число
восстановление равняется количетсву делителей...в пределах 1e5 это нормально...
AF
восстановление равняется количетсву делителей...в пределах 1e5 это нормально...
Я полагаю их всеравно ему перебирать надо потом