Dada una array arr[] que consta de N enteros, cada elemento de la array arr[i] representa los coeficientes de una expresión polinomial que comienza con el grado más alto ( A[0].X (N – 1) + A[1].X ( N – 2) + … + A[N – 2].X + A[N – 1]) , la tarea es verificar si la ecuación dada es irreducible o no por el Criterio de Irreductibilidad de Eisenstein o no. Si se encuentra que es cierto , escriba Sí . De lo contrario , imprima No.
Ejemplos:
Entrada: arr[] = {4, 7, 21, 28}
Salida: Sí
Explicación:
La array dada arr[] representa el polinomio 4x 3 + 7x 2 + 21x + 28.
El número primo 7 satisface las condiciones de las condiciones de irreductibilidad de Eisenstein y por lo tanto, el polinomio es irreducible.Entrada: arr[] = {1, 2, 1}
Salida: No
Enfoque: Considere F(x) = a n x n + a n – 1 x n – 1 + … + a 0 . Las condiciones que deben cumplirse para satisfacer el Criterio de Irreductibilidad de E isenstein son las siguientes:
- Existe un número primo P tal que:
- P no divide a n .
- P divide todos los demás coeficientes, es decir, a N – 1, a N – 2 , …, a 0 .
- P 2 no divide a 0 .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos M a -1, que almacene el valor máximo de A .
- Cree un vector , digamos primo[] que contenga todos los números primos menores que e iguales a A.
- Recorra la array de números primos y para cada índice actual i, haga lo siguiente:
- Compruebe si el número primo actual primes[i] satisface las 3 condiciones, es decir,
- A[0] no es divisible por primos[i] .
- Todos los números de A[1] a A[N – 1] son todos divisibles por primos[i] .
- Un [N-1] no es divisible por primos[i] .
- Si el número satisface las tres condiciones, el polinomio es irreducible, por lo tanto, imprima Sí . De lo contrario , imprima No.
- Compruebe si el número primo actual primes[i] satisface las 3 condiciones, es decir,
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to to implement the sieve
// of eratosthenes
vector<int> SieveOfEratosthenes(int M)
{
// Stores the prime numbers
bool isPrime[M + 1];
// Initialize the prime numbers
memset(isPrime, true,
sizeof(isPrime));
for (int p = 2; p * p <= M; p++) {
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of
// p as non-prime
for (int i = p * p;
i <= M; i += p) {
isPrime[i] = false;
}
}
}
// Stores all prime numbers less
// than M
vector<int> prime;
for (int i = 2; i <= M; i++) {
// If the i is the prime numbers
if (isPrime[i]) {
prime.push_back(i);
}
}
// Return array having the primes
return prime;
}
// Function to check whether the three
// conditions of Eisenstein's
// Irreducibility criterion for prime P
bool check(int A[], int P, int N)
{
// 1st condition
if (A[0] % P == 0)
return 0;
// 2nd condition
for (int i = 1; i < N; i++)
if (A[i] % P)
return 0;
// 3rd condition
if (A[N - 1] % (P * P) == 0)
return 0;
return 1;
}
// Function to check for Eisensteins
// Irreducubility Criterion
bool checkIrreducibilty(int A[], int N)
{
// Stores the largest element in A
int M = -1;
// Find the maximum element in A
for (int i = 0; i < N; i++) {
M = max(M, A[i]);
}
// Stores all the prime numbers
vector<int> primes
= SieveOfEratosthenes(M + 1);
// Check if any prime
// satisfies the conditions
for (int i = 0;
i < primes.size(); i++) {
// Function Call to check
// for the three conditions
if (check(A, primes[i], N)) {
return 1;
}
}
return 0;
}
// Driver Code
int main()
{
int A[] = { 4, 7, 21, 28 };
int N = sizeof(A) / sizeof(A[0]);
cout << checkIrreducibilty(A, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to to implement the sieve
// of eratosthenes
static ArrayList<Integer> SieveOfEratosthenes(int M)
{
// Stores the prime numbers
boolean []isPrime = new boolean[M + 1];
// Initialize the prime numbers
for(int i = 0; i < M + 1; i++)
isPrime[i] = true;
for(int p = 2; p * p <= M; p++)
{
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true)
{
// Update all multiples of
// p as non-prime
for(int i = p * p; i <= M; i += p)
{
isPrime[i] = false;
}
}
}
// Stores all prime numbers less
// than M
ArrayList<Integer> prime = new ArrayList<Integer>();
for(int i = 2; i <= M; i++)
{
// If the i is the prime numbers
if (isPrime[i])
{
prime.add(i);
}
}
// Return array having the primes
return prime;
}
// Function to check whether the three
// conditions of Eisenstein's
// Irreducibility criterion for prime P
static int check(int []A, int P, int N)
{
// 1st condition
if (A[0] % P == 0)
return 0;
// 2nd condition
for(int i = 1; i < N; i++)
if (A[i] % P != 0)
return 0;
// 3rd condition
if (A[N - 1] % (P * P) == 0)
return 0;
return 1;
}
// Function to check for Eisensteins
// Irreducubility Criterion
static int checkIrreducibilty(int []A, int N)
{
// Stores the largest element in A
int M = -1;
// Find the maximum element in A
for(int i = 0; i < N; i++)
{
M = Math.max(M, A[i]);
}
// Stores all the prime numbers
ArrayList<Integer> primes = SieveOfEratosthenes(M + 1);
// Check if any prime
// satisfies the conditions
for(int i = 0; i < primes.size(); i++)
{
// Function Call to check
// for the three conditions
if (check(A, primes.get(i), N) == 1)
{
return 1;
}
}
return 0;
}
// Driver Code
public static void main(String[] args)
{
int []A = { 4, 7, 21, 28 };
int N = A.length;
System.out.print(checkIrreducibilty(A, N));
}
}
// This code is contributed by avijitmondal1998
Python3
# Python3 program for the above approach # Function to to implement the sieve # of eratosthenes def SieveOfEratosthenes(M): # Stores the prime numbers isPrime = [True]*(M + 1) for p in range(2, M + 1): if p * p > M: break # If isPrime[p] is not changed, # then it is a prime if (isPrime[p] == True): # Update all multiples of # p as non-prime for i in range(p * p, M + 1, p): isPrime[i] = False # Stores all prime numbers less # than M prime = [] for i in range(2, M + 1): # If the i is the prime numbers if (isPrime[i]): prime.append(i) # Return array having the primes return prime # Function to check whether the three # conditions of Eisenstein's # Irreducibility criterion for prime P def check(A, P, N): # 1st condition if (A[0] % P == 0): return 0 # 2nd condition for i in range(1,N): if (A[i] % P): return 0 # 3rd condition if (A[N - 1] % (P * P) == 0): return 0 return 1 # Function to check for Eisensteins # Irreducubility Criterion def checkIrreducibilty(A, N): # Stores the largest element in A M = -1 # Find the maximum element in A for i in range(N): M = max(M, A[i]) # Stores all the prime numbers primes = SieveOfEratosthenes(M + 1) # Check if any prime # satisfies the conditions for i in range(len(primes)): # Function Call to check # for the three conditions if (check(A, primes[i], N)): return 1 return 0 # Driver Code if __name__ == '__main__': A = [4, 7, 21, 28] N = len(A) print (checkIrreducibilty(A, N)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to to implement the sieve
// of eratosthenes
static List<int> SieveOfEratosthenes(int M)
{
// Stores the prime numbers
bool []isPrime = new bool[M + 1];
// Initialize the prime numbers
for(int i = 0; i < M + 1; i++)
isPrime[i] = true;
for(int p = 2; p * p <= M; p++)
{
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true)
{
// Update all multiples of
// p as non-prime
for(int i = p * p; i <= M; i += p)
{
isPrime[i] = false;
}
}
}
// Stores all prime numbers less
// than M
List<int> prime = new List<int>();
for(int i = 2; i <= M; i++)
{
// If the i is the prime numbers
if (isPrime[i])
{
prime.Add(i);
}
}
// Return array having the primes
return prime;
}
// Function to check whether the three
// conditions of Eisenstein's
// Irreducibility criterion for prime P
static int check(int []A, int P, int N)
{
// 1st condition
if (A[0] % P == 0)
return 0;
// 2nd condition
for(int i = 1; i < N; i++)
if (A[i] % P !=0)
return 0;
// 3rd condition
if (A[N - 1] % (P * P) == 0)
return 0;
return 1;
}
// Function to check for Eisensteins
// Irreducubility Criterion
static int checkIrreducibilty(int []A, int N)
{
// Stores the largest element in A
int M = -1;
// Find the maximum element in A
for(int i = 0; i < N; i++)
{
M = Math.Max(M, A[i]);
}
// Stores all the prime numbers
List<int> primes = SieveOfEratosthenes(M + 1);
// Check if any prime
// satisfies the conditions
for(int i = 0; i < primes.Count; i++)
{
// Function Call to check
// for the three conditions
if (check(A, primes[i], N) == 1)
{
return 1;
}
}
return 0;
}
// Driver Code
public static void Main()
{
int []A = { 4, 7, 21, 28 };
int N = A.Length;
Console.Write(checkIrreducibilty(A, N));
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program for the above approach
// Function to to implement the sieve
// of eratosthenes
function SieveOfEratosthenes(M)
{
// Stores the prime numbers
let isPrime = new Array(M + 1).fill(true);
for (let p = 2; p * p <= M; p++) {
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of
// p as non-prime
for (let i = p * p;
i <= M; i += p) {
isPrime[i] = false;
}
}
}
// Stores all prime numbers less
// than M
let prime = [];
for (let i = 2; i <= M; i++) {
// If the i is the prime numbers
if (isPrime[i]) {
prime.push(i);
}
}
// Return array having the primes
return prime;
}
// Function to check whether the three
// conditions of Eisenstein's
// Irreducibility criterion for prime P
function check(A, P, N)
{
// 1st condition
if (A[0] % P == 0)
return 0;
// 2nd condition
for (let i = 1; i < N; i++)
if (A[i] % P)
return 0;
// 3rd condition
if (A[N - 1] % (P * P) == 0)
return 0;
return 1;
}
// Function to check for Eisensteins
// Irreducubility Criterion
function checkIrreducibilty(A, N)
{
// Stores the largest element in A
let M = -1;
// Find the maximum element in A
for (let i = 0; i < N; i++) {
M = Math.max(M, A[i]);
}
// Stores all the prime numbers
let primes
= SieveOfEratosthenes(M + 1);
// Check if any prime
// satisfies the conditions
for (let i = 0;
i < primes.length; i++) {
// Function Call to check
// for the three conditions
if (check(A, primes[i], N)) {
return 1;
}
}
return 0;
}
// Driver Code
let A = [ 4, 7, 21, 28 ];
let N = A.length;
document.write(checkIrreducibilty(A, N));
</script>
Producción:
1
Complejidad temporal: O(M + N*P), donde M es el elemento máximo del arreglo y P es el número de números primos menor que N
Espacio auxiliar: O(P)