Diberikan polinomial, tentukan apakah itu prima.

Polinomial adalah ax^n + bx^(n-1) + ... + dx^3 + ex^2 + fx + g, di mana setiap istilah adalah bilangan konstan (koefisien) dikalikan dengan kekuatan bilangan bulat tidak negatif dari x. Kekuatan tertinggi dengan koefisien bukan nol disebut derajat. Untuk tantangan ini, kami hanya mempertimbangkan polinomial paling sedikit derajat 1. Artinya, setiap polinomial mengandung beberapa x. Selain itu, kami hanya menggunakan polinomial dengan koefisien bilangan bulat.

Polinomial dapat dikalikan. Misalnya, (x+3)(2x^2-2x+3)sama dengan 2x^3+4x^2-3x+9. Dengan demikian, 2x^3+4x^2-3x+9dapat difaktorkan menjadi x+3dan 2x^2-2x+3, sehingga bersifat komposit.

Polinomial lain tidak dapat difaktorkan. Misalnya, 2x^2-2x+3bukan produk dari dua polinomial (mengabaikan polinomial konstan atau yang memiliki koefisien non-integer). Karenanya, ini prima (juga dikenal sebagai irreducible).

Aturan

• Input dan output dapat melalui cara standar apa pun.
• Input dapat berupa string seperti 2x^2-2x+3, daftar koefisien seperti {2,-2,3}, atau sarana serupa lainnya.
• Output adalah nilai kebenaran jika itu prima, atau nilai falsey jika itu komposit. Anda harus menghasilkan nilai kebenaran yang sama untuk semua bilangan prima, dan nilai falsey yang sama untuk semua polinomial komposit.
• Input akan setidaknya dari derajat 1 dan paling banyak derajat 10.
• Anda tidak boleh menggunakan alat bawaan untuk faktorisasi (bilangan bulat atau ekspresi) atau pemecahan persamaan.

Contohnya

Benar - prima

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

Salah - komposit

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 byte

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

Penjelasan :

Metode Kronecker digunakan di sini. Metode ini menghasilkan polinomial tingkat rendah tertentu dan menguji apakah ada faktor polinomial asli.

Kasus uji :

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

Dibutuhkan 14-an di laptop saya untuk menyimpulkan bahwa 3x^9-8x^8-3x^7+2x^3-10itu prima.

PARI / GP, 16 byte, murah sekali

Untuk beberapa alasan ini tidak dianulir (mencatat bahwa perintah tidak memperhitungkan faktor atau persamaan):

polisirreducible

Kasus cobaan

%(x^2+x+1)

mengembalikan 1(true). Contoh lain bekerja dengan cara yang sama.

Tetapi untuk menunjukkan bahwa ini bisa dipecahkan dengan cara yang sulit, inilah solusi lengkapnya.

Lebih murah, tapi sloooooooooow

Tidak ada gunanya bermain golf ini.

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
}

Sunting: Para komentator telah menunjukkan bahwa metode pertama mungkin dilarang oleh selera yang baik, semangat aturan, Konvensi Jenewa, aturan celah standar, dll. Saya tidak setuju, tetapi dalam hal apa pun saya memposting versi kedua bersama dengan yang pertama dan tentu saja tampaknya dapat diterima.