Memfaktorkan bilangan bulat Gaussian

23

Sebuah Gaussian bilangan bulat adalah bilangan kompleks yang bagian real dan imajiner adalah bilangan bulat.

Bilangan bulat Gaussian, seperti bilangan bulat biasa, dapat direpresentasikan sebagai produk bilangan prima Gaussian, dengan cara yang unik. Tantangannya di sini adalah untuk menghitung konstituen utama dari bilangan bulat Gaussian yang diberikan.

Input: bilangan bulat Gaussian, yang tidak sama dengan 0 dan bukan unit (yaitu 1, -1, i dan -i tidak dapat diberikan sebagai input). Gunakan format apa pun yang masuk akal, misalnya:

  • 4-5i
  • -5 * j + 4
  • (4, -5)

Output: daftar bilangan bulat Gaussian, yang merupakan bilangan prima (yaitu tidak ada satupun yang dapat direpresentasikan sebagai produk dari dua bilangan bulat Gaussian non-unit), dan yang produknya sama dengan nomor input. Semua angka dalam daftar output harus non-sepele, yaitu bukan 1, -1, i atau -i. Segala format output yang masuk akal dapat digunakan; tidak harus sama dengan format input.

Jika daftar output memiliki lebih dari 1 elemen, maka beberapa output yang benar dimungkinkan. Misalnya, untuk input 9 output bisa [3, 3] atau [-3, -3] atau [3i, -3i] atau [-3i, 3i].

Test case, (diambil dari tabel ini ; 2 baris per test case)

2
1+i, 1-i

3i
3i

256
1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i

7+9i
1+i,2−i,3+2i

27+15i
1+i,3,7−2i

6840+585i
-1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i

Fungsi bawaan untuk memfaktorkan bilangan bulat Gaussian tidak diizinkan. Anjak bilangan bulat biasa dengan fungsi bawaan diizinkan.

anatolyg
sumber
Harus 3ikembali sebagai 3,i, atau 3i?
Nilai Tinta
3iadalah jawaban yang benar karena ibukan yang utama. Saya telah memperbarui test case untuk membuatnya lebih jelas.
anatolyg
apakah -3-2j, 2-1j, -1-1j jawaban yang benar untuk faktorisasi 7 + 9j?
mdahmoune
4
Menurut Wolfram Alpha, 6840+585imemiliki daftar faktor yang salah, karena 5bukan perdana Gaussian. Sebaliknya, ia kembali -1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i. Sumber
Nilai Tinta
1
FYI, 256=(1+i)**16bukan (1+i)**8karena 256=2**8=(2i)**8dan2i=(1+i)**2
Shieru Asakoto

Jawaban:

4

Jelly , 61 55 byte

Ḟ,Ċ1ḍP
Ḟ,ĊḤp/-,1p`¤×€×1,ıFs2S€⁸÷ÇÐfỊÐḟ1;Ṫð,÷@\ḟ1
Ç€F$ÐL

Cobalah online! (Header dan Footer memformat output)

-6 byte terima kasih kepada @EricTheOutgolfer

Bagaimana itu bekerja

Ḟ,Ċ1ḍP  - helper function: determines if a complex number is Gaussian
Ḟ,Ċ       - real, complex components
   1ḍ     - set each to if 1 divides them
     P    - all

Ḟ,ĊḤp/-,1p`¤×€×1,ıFs2S€⁸÷ÇÐfỊÐḟ1;Ṫð,÷@\ḟ1 - helper: outputs a factor pair of the input
Ḟ,ĊḤp/                   - creates a list of possible factors a+bi, a,b>=0
      -,1p`¤×€           - extend to the other three quadrants 
              ×1,ıFs2S€  - convert to  actual complex numbers 
⁸÷                       - get quotient with input complex number
  ÇÐf                    - keep only Gaussian numbers (using helper function)
     ỊÐḟ                 - remove units (i,-i,1,-1)
        1;               - append a 1 to deal with primes having no non-unit factors
          Ṫð,÷@\         - convert to a factor pair
                ḟ1       - remove 1s
Ç€F$ÐL
Ç€      - factor each number
   $    - and
  F     - flatten the list
    ÐL  - until factoring each number and flattening does not change the list
fireflame241
sumber
ketika ini mengatakan "keep only Gaussian" apakah itu berarti "keep Primes saja"?
don bright
@donbright tidak, ini merujuk pada menjaga hanya angka-angka kompleks dengan komponen nyata dan kompleks integer
fireflame241
@ fireflame241 oh saya mengerti sekarang! terima kasih banyak
jangan terang
5

Ruby , 258 256 249 246 + 8 = 264 257 254 byte

Menggunakan -rprime bendera.

Ya ampun, benar-benar berantakan.

Menggunakan algoritma ini dari stackoverflow.

->c{m=->x,y{x-y*eval("%d+%di"%(x/y).rect)};a=c.abs2.prime_division.flat_map{|b,e|b%4<2?(1..e).map{k=(2..d=b).find{|n|n**(~-b/2)%b==b-1}**(~-b/4)%b+1i;d,k=k,m[d,k]while k!=0;c/=d=m[c,d]==0?d:d.conj;d}:(c/=b<3?(b=1+1i)**e:b**e/=2;[b]*e)};a[0]*=c;a}

Cobalah online!

Nilai Tinta
sumber
5

Python 2 , 250 239 223 215 byte

e,i,w=complex,int,abs
def f(*Z):
 if Z:
	z=Z[0];q=i(w(z));Q=4*q*q
	while Q>0:
 	 a=Q/q-q;b=Q%q-q;x=e(a,b)
 	 if w(x)>1:
		y=z/x
		if w(y)>1 and y==e(i(y.real),i(y.imag)):f(x,y);z=Q=0
 	 Q-=1
	if z:print z
	f(*Z[1:])

Cobalah online!

  • -11 byte saat menggunakan Argumen Fungsi Berganda
  • -2² * ² byte saat menggunakan satu variabel untuk mem-parsing pasangan (a,b)
  • -2³ byte saat mencampur tab dan spasi: terima kasih kepada ovs

Beberapa penjelasan secara rekursi menguraikan kompleks menjadi dua kompleks sampai tidak ada pembusukan yang mungkin ...

mdahmoune
sumber
Yah, ini sudah habis di TIO pada input yang lebih besar, tetapi lebih pendek dari jawaban Ruby saya ... untuk saat ini . Juga, def f(Z,s=[])harus menyelamatkan Anda karakter
Nilai Tinta
@ ValueInk ya itu lebih lambat daripada solusi ruby ​​Anda
mdahmoune
2
Pola yang menarik dengan lekukan ...
Erik the Outgolfer
@NilaiInk Beberapa Fungsi Argumen menghemat lebih banyak byte :)
mdahmoune
1
Anda dapat mengurangi jumlah byte Anda dengan mencampur tab dan spasi
ovs
3

Karat - 212 byte

use num::complex::Complex as C;fn f(a:&mut Vec<C<i64>>){for _ in 0..2{for x in -999..0{for y in 1..999{for i in 0..a.len(){let b=C::new(x,y);if(a[i]%b).norm_sqr()==0&&(a[i]/b).norm_sqr()>1{a[i]/=b;a.push(b)}}}}}}

Saya tidak 100% yakin apakah ini berfungsi 100% benar, tetapi tampaknya benar untuk berbagai macam tes. Ini tidak lebih kecil dari Jelly, tapi setidaknya itu lebih kecil dari bahasa yang ditafsirkan (sejauh ini). Ini juga tampaknya lebih cepat dan dapat bekerja melalui input yang besarnya satu miliar dalam waktu kurang dari satu detik. Misalnya 1234567890 + 3141592650i faktor sebagai (-9487 + 7990i) (- 1 + -1i) (- 395 + 336i) (2 + -1i) (1 + 1i) (3 + 0i) (3 + 0i) (3 + 0i) (4+ 1i) (- 1 + 1i) (- 1 + 2i), (klik di sini untuk menguji wolfram alpha)

Ini dimulai sebagai ide yang sama seperti anjak bilangan bulat dari bilangan bulat, untuk melewati setiap angka di bawah bilangan bulat yang dimaksud, lihat apakah ia terbagi, ulangi sampai selesai. Kemudian, terinspirasi oleh jawaban lain, itu berubah ... berulang kali faktor item dalam vektor. Ini melakukan ini beberapa kali, tetapi tidak 'sampai' apa pun. Jumlah iterasi telah dipilih untuk mencakup sejumlah input yang masuk akal.

Itu masih menggunakan "(a mod b) == 0" untuk menguji apakah satu integer membagi yang lain (untuk Gaussians, kami menggunakan builtin Rust gaussian modulo, dan menganggap "0" sebagai norma == 0), namun pemeriksaan untuk 'norma ( a / b)! = 1 'mencegah membagi "terlalu banyak", pada dasarnya memungkinkan vektor yang dihasilkan hanya diisi dengan bilangan prima, tetapi tidak mengambil elemen vektor ke kesatuan (0-i, 0 + i, -1 + 0i, 1 + 0i) (yang dilarang oleh pertanyaan).

Batas for-loop ditemukan melalui percobaan. Anda beralih dari 1 ke atas untuk mencegah kepanikan di-by-zero, dan x dapat berubah dari -999 menjadi 0 berkat mirroring Gaussians atas kuadran (saya pikir?). Mengenai keterbatasan, pertanyaan awal tidak menunjukkan kisaran input / output yang valid, sehingga "ukuran input yang masuk akal" diasumsikan ... (Edit ... namun saya tidak yakin bagaimana menghitung di nomor mana ini akan mulai "gagal", saya bayangkan ada bilangan bulat Gaussian yang tidak dapat dibagi oleh apa pun di bawah 999 tetapi masih sangat kecil bagi saya)

Coba versi yang agak ungolfed di play.rust-lang.org

jangan cerah
sumber
3

Perl 6 , 141 124 byte

Terima kasih kepada Jo King untuk -17 byte

sub f($_){{$!=0+|sqrt .abs²-$^a²;{($!=$_/my \w=$^b+$a*i)==$!.floor&&.abs>w.abs>1>return f w&$!}for -$!..$!}for ^.abs;.say}

Cobalah online!

bb94
sumber
bagaimana cara kerjanya? Apakah lantai merupakan modulo yang dibuat khusus?
don cerah
1
@donbright Bagian floorini memeriksa apakah $_/w(yaitu faktor saat ini dibagi dengan angka) adalah bilangan bulat
Jo King
2

Pyth , 54 51 45 42 36 byte

 .W>H1cZ
h+.aDf!%cZT1>#1.jM^s_BM.aZ2

Cobalah online!

Menerima input dalam bentuk 1+2j- angka nyata atau imajiner murni dapat menghilangkan komponen lain (misalnya 9, 2j). Output adalah daftar bilangan kompleks yang dipisahkan oleh baris baru, dalam formulir(1+2j) , dengan bilangan imajiner murni menghilangkan bagian yang sebenarnya.

Ini menggunakan pembagian jejak sederhana, menghasilkan semua bilangan bulat gaussian dengan magnitudo lebih besar dari 1 dan kurang dari nilai saat ini, ditambah nilainya sendiri. Ini disaring untuk menjaga mereka yang merupakan faktor nilai, dan yang terkecil berdasarkan besarnya dipilih sebagai faktor utama berikutnya. Ini adalah output, dan nilainya dibagi olehnya untuk menghasilkan nilai untuk iterasi berikutnya.

Juga, Pyth mengalahkan Jelly 😲 (saya tidak berharap itu berlangsung lama)

 .W>H1cZ¶h+.aDf!%cZT1>#1.jM^s_BM.aZ2ZQ   Implicit: Q=eval(input())
                                         Newline replaced with ¶, trailing ZQ inferred
 .W                                  Q   While <condition>, execute <inner>, with starting value Q
   >H1                                   Condition function, input H
   >H1                                     Is magnitude of H > 1?
                                           This ensures loop continues until H is a unit, i.e. 1, -1, j, or -j)
      cZ¶h+.aDf!%cZT1>#1.jM^s_BM.aZ2Z    Inner function, input Z
                                .aZ        Take magnitude of Z

                             _BM           Pair each number in 0-indexed range with its negation
                            s              Flatten
                           ^       2       Cartesian product of the above with itself
                        .jM                Convert each pair to a complex number
                      #                    Filter the above to keep those element where...
                     > 1                   ... the magnitude is greater than 1 (removes units)
              f                            Filter the above, as T, to keep where:
                 cZT                         Divide Z by T
                %   1                        Mod real and imaginary parts by 1 separately
                                             If result of division is a gaussian integer, the mod will give (0+0j)
               !                             Logical NOT - maps (0+0j) to true, all else to false
                                           Result of filter are those gaussian integers which evenly divide Z
           .aD                             Sort the above by their magnitudes
          +                         Z      Append Z - if Z is ±1±1j, the filtered list will be empty
         h                                 Take first element, i.e. smallest factor
        ¶                                  Print with a newline
      cZ                                   Divide Z by that factor - this is new input for next iteration
                                         Output of the while loop is always 1 (or -1, j, or -j) - leading space suppesses output
Sok
sumber
ini sangat menarik tetapi tampaknya batas waktu pada 6840 + 585j
don cerah
@donbright Hal ini berlaku pada TIO, karena memiliki batas pemrosesan 60-an. Ini akan bekerja dengan lebih banyak waktu, jadi jika Anda menjalankannya secara lokal itu akan berfungsi tanpa masalah.
Sok