Страницы

Поиск по вопросам

четверг, 11 октября 2018 г.

Реализация поиска простых делителей

Всем привет, написал код по поиску простых чисел и запоминания этих чисел и их степеней:
int t = 0; int i = 2; int k = 1; int z = 0; vector q(10); vector ak(10); int l=phi(p); t = l;
while (i <= t) { if (t%i == 0) { t = t / i; q[z] = i; ak[z] = k; k++; if (t%i != 0) { z++; k = 1; } } else { i = i + 1; } } }
Получилось очень много кода. Подскажите, пожалуйста, как можно оптимизировать


Ответ

Я бы не сказал, что его много, его просто мало :), но он не очень удобен и эффективен. Держать два массива для делителей и степеней - неудобно, тем более что это тесно взаимосвязанные вещи. Проще использовать map
Далее, перебирать все делители тоже смысла не имеет - ну зачем после проверки деления на 2 проверять, например, деление на 6? Идеально для скорости - хранить массив простых чисел и работать с ним; но если это кажется напрасной тратой места :) - то хотя бы проходите просто по нечетным числам, вынеся работу с двойками отдельно.
Словом, я бы предложил такое
map factorize(unsigned int n) { map m; while(n > 1 && n%2 == 0) { m[2]++; n /= 2; } if (n > 1) for(unsigned int i = 3; i*i <= n;) { if (n%i == 0) { m[i]++; n /= i; continue; } i += 2; } if (n > 1) m[n]++; return m; }
Еще раз - я бы этот код дополнил таблицей простых чисел...
И еще - малое количество кода - не всегда означает эффективное решение. Нередко лучше написать в два раза больше кода, но получить в несколько раз более быстрое решение.

Комментариев нет:

Отправить комментарий