Étant donné un polynôme, déterminez s'il est premier.

Un polynôme est ax^n + bx^(n-1) + ... + dx^3 + ex^2 + fx + g, où chaque terme est un nombre constant (le coefficient) multiplié par une puissance entière non négative de x. La puissance la plus élevée avec un coefficient non nul s'appelle le degré. Pour ce défi, nous considérons uniquement des polynômes d'au moins degré 1. Autrement dit, chaque polynôme en contient x. De plus, nous utilisons uniquement des polynômes avec des coefficients entiers.

Les polynômes peuvent être multipliés. Par exemple, (x+3)(2x^2-2x+3)est égal à 2x^3+4x^2-3x+9. Ainsi, 2x^3+4x^2-3x+9peut être pris en compte dans x+3et 2x^2-2x+3, il est donc composite.

D'autres polynômes ne peuvent pas être pris en compte. Par exemple, 2x^2-2x+3n'est pas le produit de deux polynômes (en ignorant les polynômes constants ou ceux avec des coefficients non entiers). Par conséquent, il est premier (également appelé irréductible).

Règles

• L'entrée et la sortie peuvent se faire par n'importe quel moyen standard.
• L'entrée peut être une chaîne 2x^2-2x+3, une liste de coefficients {2,-2,3}ou tout autre moyen similaire.
• La sortie est soit une valeur véridique si elle est première, soit une valeur de falsey si elle est composite. Vous devez fournir la même valeur véridique pour tous les nombres premiers et la même valeur de falsey pour tous les polynômes composites.
• L'entrée sera au moins de degré 1 et au plus de degré 10.
• Vous ne pouvez pas utiliser d'outils intégrés pour la factorisation (d'entiers ou d'expressions) ou la résolution d'équations.

Exemples

Vrai - premier

x+3
-2x
x^2+x+1
x^3-3x-1
-2x^6-3x^4+2
3x^9-8x^8-3x^7+2x^3-10

Faux - composite

x^2
x^2+2x+1
x^4+2x^3+3x^2+2x+1
-3x^7+5x^6-2x
x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12

Mathematica, 224 octets

f@p_:=(e=p~Exponent~x;r=Range[⌈e/-4⌉,(e+2)/4];e<2||FreeQ[PolynomialRemainder[p,Thread@{r,#}~InterpolatingPolynomial~x,x]&/@Tuples[#~Join~-#&[Join@@Position[#/Range@Abs@#,_Integer]]&/@#]~DeleteCases~{(a_)..},0|{}]&[p/.x->r])

Explication :

La méthode de Kronecker est utilisée ici. Cette méthode génère certains polynômes de degré inférieur et vérifie s'il existe un facteur du polynôme d'origine.

Cas de test :

f/@{x+3, -2x, x^2+x+1, x^3-3x-1, -2x^6-3x^4+2, 3x^9-8x^8-3x^7+2x^3-10}
(* {True, True, True, True, True, True} *)

f/@{x^2, x^2+2x+1, x^4+2x^3+3x^2+2x+1, -3x^7+5x^6-2x, x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12}
(* {True, True, True, True, True} *)

Il faut 14 secondes sur mon ordinateur portable pour conclure que 3x^9-8x^8-3x^7+2x^3-10c'est parfait.

PARI / GP, 16 octets, pas cher comme l'enfer

Pour une raison quelconque, cela n'a pas été interdit (en notant que la commande ne factorise pas ou ne résout pas l'équation):

polisirreducible

Cas de test

%(x^2+x+1)

renvoie 1(vrai). Les autres exemples fonctionnent de manière similaire.

Mais pour montrer que cela est résoluble à la dure, voici une solution complète.

Moins cher, mais sloooooooooow

Cela ne sert à rien de jouer au golf.

Beauzamy(P)=
{
  my(d=poldegree(P),s,c);
  s=sum(i=0,d,polcoeff(P,i)^2/binomial(d,i));
  c = 3^(3/2 + d);
  c *= s / (4*d*Pi);
  abs(c * pollead(P))
}
factorpol(P)=
{
  my(B=Beauzamy(P)\1, t=B*2+1, d=poldegree(P)\2, Q);
  for(i=0,t^(d+1)-1,
    Q=Pol(apply(n->n-B, digits(i,t)));
    if(Q && poldegree(Q) && P%Q==0, return(Q))
  );
  0
}
irr(P)=
{
  factorpol(P)==0
}

Edit: Les commentateurs ont souligné que la première méthode peut être rejetée par le bon goût, l'esprit des règles, la Convention de Genève, les règles standard des échappatoires, etc. Je ne suis pas d'accord, mais en tout cas j'ai posté la deuxième version avec le premier et certainement cela semble acceptable.