Ребята, мне надо найти разложения на простые множители всех чисел

Question

Ребята, мне надо найти разложения на простые множители всех чисел

до n=10^5, желательно побыстрее. Вопрос:
1) Правильно ли я понимаю, что лучше делать по типу решета эратосфена: идти по массиву чисел с простым шагом р и делить каждое по максимуму на это р?
2) Как лучше хранить найденные факторизации? Я собираюсь в виде массива длиной n из структур вида
struct prime_factors {
int primes[8];
int exp[8];
};
Это нормально? Или лучше как-то по другому?

#c #embedded #programming #russian

0

19.07.2020

5 ответов

8 просмотров

Danya🔥

@proalgorithms кажется это сюда

0

19.07.2020

Aidar Fattakhov

Кажется да

0

19.07.2020

Владимир

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_ {};

0

19.07.2020

Sher M

нужно хранить минимальный простой делитель для каждого из чисел...по ним возмжно будет восстановить общий ответ....время работы алгоритма O (n)

0

19.07.2020

Пользователь 61adb · Accepted Answer

Пользователь 61adb

Решето нужно не для факторизации

0

19.07.2020

170 похожих чатов

Ребята, мне надо найти разложения на простые множители всех чисел

5 ответов

Похожие вопросы