Как найти простые множители числа c
Перейти к содержимому

Как найти простые множители числа c

  • автор:

Ускорить алгоритм разложения числа на простые множители

Написал алгоритм который разложить число на простые множители, работает хорошо, но медленно. Не засчитывает 2 теста, исчерпан лимит времени. Входное число, которое нужно разложить в пределах от 1 до 2 (на 31 степени) -1. Учёл ввод простого числа, так что это не должно мешать, да и не в нём дело, те 2 теста, которые не проходят по времени не предоставляют простое число, проверял выводом n-1 для любого случая. Как можно ускорить это ?

#include #include using namespace std; int rozout(long long n); bool prime(long long n); int main() < long long n; cin >> n; if (prime(n)) < cout rozout(n); > int rozout(long long n) < long long i = 2; while (n >1) < while (n % i == 0) < cout if (i return 1; > bool prime(long long n) < long double S = sqrt(n); for (long long i = 2; i > return true; > 

Отслеживать
12.6k 2 2 золотых знака 19 19 серебряных знаков 46 46 бронзовых знаков
задан 13 дек 2020 в 19:56
golderzert golderzert
31 3 3 бронзовых знака

Разложение тоже делается за корень: если у числа есть какое-то простое P в разложении, которое больше, чем sqrt(N), то оно ровно одно, так как иначе произведение двух таких уже больше N. Таким образом, обычно пишется цикл от двух до sqrt(N) (включительно) и для каждого числа считается, сколько раз на него можно разделить N. Если после цикла N не равен 1, то это получившееся N — простое, входящее в разложение.

13 дек 2020 в 20:20

И соответственно простейший тест, ломающий вашу программу — это любое большое удвоенное простое, например 2 * (10 ^ 9 + 7)

13 дек 2020 в 20:22
Посмотрите ru.stackoverflow.com/q/595966/195342
13 дек 2020 в 20:36

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

Быстрое элементарное разложение. Если число — ноль или один, печатаем его. Иначе выделяем из числа двойки — делим на два пока делится. Затем перебираем нечётные числа начиная с трёх и проверяем делимость. Если делится, то делим пока делится. Можно показать, что хотя перебираются все нечётные числа, на печать попадут только простые. Поиск завершается когда возможный делитель добрался до √n. Дальше искать нет смысла: если n разлагается в произведение, один из множителей должен быть не больше корня. После цикла добавляем в разложение n, если оно ещё больше единицы.

Если в цикле найден делитель, n уменьшается и обновляется значение √n. Корень считается через std::sqrt(double) . Для n < 2 31 вычисления будут точными.

Цикл делает не более 23170 итераций — (√2 31 — 1) / 2. В каждой итерации делается одно сравнение ( i

Худшие по времени случаи для программы: простые числа, квадраты простых чисел, произведения двух близких простых чисел.

#include #include uint32_t isqrt(uint32_t n) < return static_cast(std::sqrt(static_cast(n))); > void print_factorization(uint32_t n) < bool first = true; auto print = [&first](uint32_t factor) < if (!first) < std::cout std::cout ; if (n else < for (; n % 2 == 0; n /= 2) < print(2); >uint32_t i = 3; uint32_t n_sqrt = isqrt(n); while (i while (n % i == 0); n_sqrt = isqrt(n); > i += 2; > if (n > 1) < print(n); >> std::cout int main() < uint32_t n; std::cin >> n; print_factorization(n); > 
$ time echo 2146654199 | ./a.out 46327*46337 real 0m0.002s user 0m0.004s sys 0m0.000s 

Разложение числа на простые множители

Author24 — интернет-сервис помощи студентам

нуна помощь с программой, где пользователь вводит список положительных целых чисел, который заканчивается нулем, а програама выписывает разложение на простые множители каждого числа из данного списка.

Например
Разложение числа 120 на простые множители:
2^3 x 3 x 5

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Разложение числа на простые множители
Мир всем. Написал вот такую вот программу для разложения числа на простые множители с.

Разложение натурального числа на простые множители
Помогите пожалуйста составить программу для разложения данного натурального числа на простые.

Разложение на простые множители заданного натурального числа
Составить программу, печатающую разложение на прос¬тые множители заданного натурального числа n > 0.

Требуется вычислить разложение натурального числа на простые множители
Простите,что пишу сюда код на си,просто дождаться ответов в разделе "Си" невозможно: Ошибка в.

2639 / 1751 / 920
Регистрация: 16.10.2013
Сообщений: 5,068
Записей в блоге: 14

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
#include #include int main(){ int num, i = 2; printf("Enter number: "); scanf("%d", &num); while(i  num){ if(num % i == 0){ printf("%d", i); num = num / i; if(num > 1) printf("*"); } else i++; } return 0; }

Разложение на множители (факторизация)

Основная теорема арифметики, вкупе с утверждением, что [math]y[/math] не делит [math]x[/math] нацело: [math]\forall x, y \in \mathbb~~x\lt y \Longrightarrow[/math] [math]\left( \dfrac \lt 1 \right)[/math] , позволяют нам ограничить пространство поиска делителей числа [math]number[/math] интервалом [math][2;number][/math] .

Основная идея

Заметим, что если [math]number[/math] = [math]\prod p_i = p_1 \cdot p_2 \cdot \ldots \cdot p_ \cdot p_j \cdot p_ \cdot \ldots \cdot p_n[/math] , то [math]\left(\dfrac\right) = \prod\limits_ p_i = p_1 \cdot p_2 \cdot \ldots \cdot p_ \cdot p_ \cdot \ldots \cdot p_n[/math] . Таким образом, мы можем делить [math]number[/math] на его делители (множители) последовательно и в любом порядке. Тогда будем хранить [math]curNum \colon curNum = \dfrac<\prod result_i>[/math] — произведение оставшихся множителей.

Псевдокод нахождения простых множителей

Так как простых множителей не может быть больше, чем [math]n[/math] , а в худшем случае (когда число простое, и на каждое итерации [math]probe[/math] увеличивается на [math]1[/math] ) он работает за [math]O(n)[/math] , то, следовательно, алгоритм работает за [math]O(n)[/math] .

function getMultipliers(number: int): vector // сюда складываем множители result = vector // число, у которого осталось найти множители curNum = number // число, на которое пытаемся делить probe = 2 while curNum [math]\ne[/math] 1 if curNum mod probe [math]\ne\, [/math]0 // проверены все множители из [2; probe] probe++ else // делим пока делится curNum /= probe result += [probe] return result
Псевдокод нахождения делителей
function getDividers(number: int): vector // массив полученных делителей result = vector // перебираем все потенциальные делители for probe = 2 to number if number mod probe = 0 // probe делит number нацело result += [probe] return result

Улучшенная реализация [math]O(\sqrt)[/math]

Основная идея

Из определения: [math]\sqrt \cdot \sqrt = n[/math] . Логично, что:

[math]\bigg\ <[/math] [math]x \cdot y = number[/math] [math]\Longrightarrow x \gt \sqrt[/math]
[math]y \lt \sqrt[/math]

Таким образом, любой делитель [math]d_0 \gt \sqrt[/math] однозначно связан с некоторым [math]d_1 \lt \sqrt[/math] . Если мы найдем все делители до [math]\sqrt[/math] , задача может считаться решенной.

Псевдокод
function getDividers(number: int): vector result = vector for probe = 2 to [math]\sqrt[/math] //обновляем верхнюю границу перебора if number mod probe = 0 result += [probe] result += [number / probe] // записываем сопряженный делитель return result

Проверка числа на простоту

Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется множителей (и делителей) кроме [math]1[/math] (алгоритмы не проверяют делимость на [math]1[/math] ) и самого числа (улучшенная реализация опускает этот делитель).

Предподсчет

Основная статья: Решето Эратосфена

Основная идея

Решето Эратосфена (англ. Sieve of Eratosthenes) позволяет не только находить простые числа, но и находить простые множители числа. Для этого необходимо хранить (помимо самого «решета») массив простых чисел, на которое каждое число делится (достаточно одного простого делителя).

Псевдокод

// возвращает только дополнительный массив function sieveOfEratosthenes(n: int): int[n + 1] result = [n + 1] result[n] = n // выбираем следующий простой делитель for i = 2 to [math]\sqrt[/math] if result[i] = 0 // записываем делитель в элементы массива, // соответствующие числа которых делятся нацело shuttle = [math]i^2[/math] while shuttle [math]\leqslant[/math] n result[shuttle] = i shuttle += i return result
function getMultipliers(number: int): vector result = vector // получаем дополненное решето Эратосфена sieve = sieveOfEratosthenes(number) // следующее временное значение получаем // делением предыдущего на простой делитель из решета curNum = number while curNum [math]\ne[/math] 1 result += sieve[curNum] curNum /= sieve[curNum] return result

См. также

  • Решето Эратосфена
  • Основная теорема арифметики
  • Комбинаторика

Источники информации

  • Маврин П.Ю. — Лекция по алгоритмам над простыми числами (2016)
  • https://ru.wikipedia.org/wiki/Простое_число
  • Алгоритмы алгебры и теории чисел
  • Теория чисел

Разложение числа на простые множители (факторизация). Делители числа

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

Из различных разделов математики в спортивном программировании чаще всего встречаются элементы элементарной теории чисел. В этом разделе значительную роль имеет разложение числа на простые множители. Простыми называются такие числа, которые не имеют делителей кроме 1 и самого себя. Ряд простых чисел выглядит так:

\[2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots\]

Все остальные натуральные числа (кроме 1) называются составными, так как их можно представить в виде произведения нескольких простых чисел. Например:

Часто это записывается со степенями простых множителей:

Таким образом, любое число можно представить в виде произведения простых множителей следующим образом:

Согласно основной теореме арифметики, каждому числу однозначно соответствует такое представление, поэтому разложение числа на простые множители тесно связано с некоторыми его свойствами, и часто используется в решении задач.

Проверка числа на простоту

Чтобы проверить, является ли натуральное число \(x\) простым, достаточно просто проверить, существует ли в отрезке \([2;\sqrt]\) число, на которое делится \(x\). Это достаточно очевидно: если бы существовало такое число \(y\), что \(x\) делится на \(y\) и \(\sqrt < y < x\), то гарантированно существовало бы и число \(z = x/y\), которое было бы меньше корня, а значит, изначального условия хватило бы для проверки на простоту.

Реализация на C++:

1 2 3 4 5 6 7 8 9
bool is_prime(int x)  for (int i = 2; i  sqrt(x); i++)  if (x % i == 0)  return false; > > return true; > 

Сложность этого алгоритма \(O(\sqrt)\). Существуют алгоритмы, позволяющие выполнять эту проверку быстрее (порядка \(O(\log^6 N)\)), но они исключительно редко применяются в спортивном программировании.

Факторизация

Факторизацией называется разложение числа на простые множители. Алгоритм факторизации основывается на тех же идеях, что и алгоритм проверки на простоту, приведённый выше. А именно: если у числа существует простой делитель, отличный от него самого, то он не превышает корня из числа. Для факторизации числа нужно перебрать все числа в промежутке \([2;\sqrt]\), и попытаться разделить \(x\) на каждое из них по очереди.

Реализация на C++ (Сложность: \(O(\sqrt)\)):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
vectorint> factorize(int x)  vectorint> factors; for (int i = 2; i  sqrt(x); i++)  while (x % i == 0)  factors.push_back(i); x /= i; > > if (x != 1)  factors.push_back(x); > return factors; > 

Корректность этого алгоритма доказать также несложно. Заметим, что если при факторизации числа \(x\) мы нашли делитель \(y\), то нам, по факту, осталось факторизовать число \(x/y\). Поэтому мы можем смело разделить число \(x\) на \(y\) и продолжить работу алгоритма. Мы можем не начинать проверку сначала, так как число \(x/y\) гарантированно не имеет делителей меньше \(y\), иначе мы бы их уже нашли при факторизации \(x\).

Также очевидно, что все множители, найденные алгоритмом будут простыми. Можно заметить, что каждый раз алгоритм находит минимальный из всех делителей числа, и делит на него само число. Минимальный возможный делитель числа всегда будет простым.

И наконец, используя доказательство из предыдущего раздела, если у числа нет делителей меньше либо равных его корню, то оно простое. Этот случай обрабатывается отдельной проверкой после цикла.

Также можно реализовать алгоритм в виде поиска пар \((p_i, \alpha_i)\), где \(p_i\) - множитель, \(\alpha_i\) - его степень:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
mapint, int> factorize(int x)  mapint, int> factors; for (int i = 2; i  sqrt(x); i++)  while (x % i == 0)  factors[i]++; x /= i; > > if (x != 1)  factors[x]++; > return factors; > 

Поиск делителей

Поиск делителей числа и разложение его на множители - разные понятия, хотя термины в какой-то степени схожи. Под делителями числа подразумевают все числа, на которые оно делится. Пример для числа 20:

Множители \(2, 2, 5\)
Делители \(1, 2, 4, 5, 10, 20\)

Алгоритм поиска делителей числа \(x\) во многом похож на другие алгоритмы, приведённые выше. Мы рассматриваем делители парами: для каждого делителя \(y\) мы учитываем соответствующий ему \(x/y\). Один из этих делителей гарантированно не превышает \(\sqrt\), поэтому, как и раньше, мы можем рассматривать только промежуток \([1;\sqrt]\).

Реализация на C++ (Сложность: \(O(\sqrt)\)):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
vectorint> find_dividers(int x)  vectorint> dividers; for (int i = 1; i  sqrt(x); i++)  if (x % i == 0)  dividers.push_back(i); //для корня из x не существует парного делителя if (i * i != x)  dividers.push_back(x / i); > > > return dividers; > 

Количество делителей

В качестве примера математических свойств представления числа в виде простых множителей приведём связь между характеристиками простых множителей числа и количеством его делителей.

Для этого давайте определим понятие делителя в контексте простых множителей. Запишем числа \(x\) и \(y\) в следующем виде:

Если какой-либо простой множитель не входит в разложение одного из чисел, то его степень в следующих рассуждениях принимается за 0.

Утверждение: частное двух чисел можно записать следующим образом:

Так как мы работаем с натуральными числами, это выражение имеет смысл тогда и только тогда, когда все степени простых множителей целые и неотрицательные. Отсюда можно выразить условие делимости двух чисел:

\[\forall i: \alpha_i - \beta_i \ge 0\]

\[\forall i: \beta_i \le \alpha_i\]

(Если вы не знакомы с подобной записью, \(\forall i\) обозначает “для всех \(i\)”)

Из этого условия можно легко вывести количество делитей. Ещё раз запишем \(x\) в виде

Вспомним, что любому натуральному числу однозначно соответствует разложение на простые множители, то есть, набор степеней. Другими словами, изменение любой степени в наборе даст нам новое уникальное число.

Давайте рассмотрим, сколько возможных значений может принимать каждая степень \(\beta_i\). С ней связано два условия:

\(\beta_i \ge 0\)
\(\beta_i \le \alpha_i\)

Значит, каждая из степеней \(\beta_i\) может принимать \(\alpha_i + 1\) различных значений, и набор степеней \(\beta\) однозначно описывает уникальный делитель. Используя формулы комбинаторики мы можем выразить количество делителей следующим образом:

\[K = (\alpha_1 + 1) * (\alpha_2 + 1) * \ldots * (\alpha_n + 1) = \prod\limits_i (\alpha_i + 1)\]

Реализация на C++:

1 2 3 4 5 6 7 8 9
int dividers_count(mapint, int>& factors)  int result = 1; for (mapint, int>::iterator it = factors.begin(); it != factors.end(); it++)  result *= it->second + 1; > return result; > 

Реализация на C++11:

1 2 3 4 5 6 7 8 9
int dividers_count(mapint, int>& factors)  int result = 1; for (auto p: factors)  result *= p.second + 1; > return result; > 

Это всего лишь одно из свойств простых множителей. Единственный способ научиться решать задачи на эту тему - практика.

brestprog

Олимпиадное программирование в Бресте и Беларуси

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *