Biorąc pod uwagę wielomian, określ, czy jest liczbą pierwszą.

Wielomianem jest ax^n + bx^(n-1) + ... + dx^3 + ex^2 + fx + g, gdzie każdy warunek jest liczbą stałą (współczynnikiem) pomnożoną przez nieujemną moc całkowitą wynoszącą x. Najwyższą moc o niezerowym współczynniku nazywa się stopniem. W przypadku tego wyzwania bierzemy pod uwagę wielomian co najmniej stopnia 1. Oznacza to, że każdy wielomian zawiera niektóre x. Używamy również wielomianów o współczynnikach całkowitych.

Wielomiany można mnożyć. Na przykład (x+3)(2x^2-2x+3)równa się 2x^3+4x^2-3x+9. W ten sposób 2x^3+4x^2-3x+9można go rozdzielić na x+3i 2x^2-2x+3dlatego jest złożony.

Inne wielomiany nie mogą być uwzględnione. Na przykład 2x^2-2x+3nie jest iloczynem dwóch dowolnych wielomianów (ignorowanie stałych wielomianów lub tych o współczynnikach niecałkowitych). Dlatego jest liczbą pierwszą (znaną również jako nieredukowalna).

Zasady

• Wejście i wyjście może odbywać się dowolnym standardowym sposobem.
• Dane wejściowe mogą być ciągiem znaków 2x^2-2x+3, listą współczynników podobnych {2,-2,3}lub dowolnymi podobnymi środkami.
• Wyjście jest albo prawdą, jeśli jest liczbą pierwszą, albo wartością falsey, jeśli jest złożone. Musisz podać tę samą prawdziwą wartość dla wszystkich liczb pierwszych i tę samą wartość falsey dla wszystkich wielomianów złożonych.
• Dane wejściowe będą co najmniej stopnia 1, a co najwyżej stopnia 10.
• Nie można używać wbudowanych narzędzi do faktoryzacji (liczb całkowitych lub wyrażeń) lub rozwiązywania równań.

Przykłady

Prawda - liczba pierwsza

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

Fałsz - kompozyt

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 bajty

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])

Objaśnienie :

Zastosowano tutaj metodę Kroneckera . Ta metoda generuje pewne wielomiany niższego stopnia i sprawdza, czy istnieje czynnik pierwotnego wielomianu.

Przypadki testowe :

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} *)

Na moim laptopie potrzeba 14 sekund, aby dojść do wniosku, że 3x^9-8x^8-3x^7+2x^3-10jest liczbą pierwszą.

PARI / GP, 16 bajtów, tanie jak diabli

Z jakiegoś powodu nie zostało to zabronione (zauważając, że polecenie nie uwzględnia ani nie rozwiązuje równań):

polisirreducible

Przypadek testowy

%(x^2+x+1)

zwraca 1(prawda). Inne przykłady działają podobnie.

Ale aby pokazać, że jest to trudne do rozwiązania, oto pełne rozwiązanie.

Mniej taniej, ale sloooooooooow

Naprawdę nie ma sensu grać w golfa.

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
}

Edycja: Komentatorzy zwrócili uwagę, że pierwsza metoda może być niedozwolona przez dobry gust, ducha zasad, Konwencję genewską, standardowe zasady dotyczące luk itp. Nie zgadzam się, ale w każdym razie opublikowałem drugą wersję wraz z pierwszy i na pewno wydaje się do przyjęcia.