Программа для проверки неприводимости с использованием критерия неприводимости Эйзенштейна

Дан массив arr[] , состоящий из N целых чисел, такой, что каждый элемент массива arr[i] представляет собой коэффициенты полиномиального выражения, начиная с высшей степени ( A[0].X ^{(N – 1)} + A[1].X ^{( N – 2)} + … + A[N – 2].X + A[N – 1]) , задача состоит в том, чтобы проверить, является ли данное уравнение неприводимым или нет по критерию неприводимости Эйзенштейна или нет. Если найдено верно , то выведите Yes . В противном случае выведите Нет .

Примеры:

Input: arr[] = {4, 7, 21, 28}
Output: Yes
Explanation:
The given array arr[] represents the polynomial 4x³ + 7x² + 21x + 28.
The prime number 7 satisfies the conditions of Eisenstein’s Irreducibility conditions and thus, the polynomial is irreducible.

Input: arr[] = {1, 2, 1}
Output: No

Подход: рассмотрим F(x) = a _n x ⁿ + _{an – 1} x ^{n – 1} + … + a _{0 .} Условия, которые необходимо выполнить, чтобы удовлетворить критерию неприводимости Эйзенштейна, следующие:

• Существует простое число P такое, что:
  • P не делит _n .
  • P делит все остальные коэффициенты, т. е. a _{N – 1,} a _{N – 2} , …, a ₀ .
  • P ² не делит ₀ .

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, M равным -1, которая хранит максимальное значение A .
• Создайте вектор, скажем, prime[] , который содержит все простые числа, меньшие и равные A .
• Пройдите через массив простых чисел и для каждого текущего индекса i сделайте следующее:
  • Проверьте, удовлетворяет ли текущее простое число primes[i] всем трем условиям, т.е.
    • A[0] не делится на primes[i] .
    • Все числа от A[1] до A[N – 1] делятся на primes[i] .
    • A [N-1] не делится на primes[i] .
  • Если число удовлетворяет всем трем условиям, многочлен неприводим, поэтому выведите Yes . В противном случае выведите Нет .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M + N*P), где M — максимальный элемент в массиве, а P — количество простых чисел меньше N.
Вспомогательное пространство: O(P)