Tugasnya adalah menemukan faktor non-sepele dari angka komposit.
Tulis kode yang menemukan faktor non-sepele dari nomor komposit secepat mungkin dengan kode Anda yang panjangnya tidak lebih dari 140 byte. Output seharusnya menjadi faktor yang Anda temukan.
Kode Anda dapat mengambil input dan memberikan output dengan cara apa pun yang nyaman termasuk misalnya sebagai argumen untuk suatu fungsi.
Uji kasus yang mencantumkan semua faktor (Anda hanya perlu menampilkan satu)
187: 11 17
1679: 23 73
14369648346682547857: 1500450271 9576890767
34747575467581863011: 3628273133 9576890767
52634041113150420921061348357: 2860486313 5463458053 3367900313
82312263010898855308580978867: 264575131106459 311111111111113
205255454905325730631914319249: 2860486313 71755440315342536873
1233457775854251160763811229216063007: 1110111110111 1000000000063 1111111999999
1751952685614616185916001760791655006749: 36413321723440003717 48112959837082048697
Saya tidak akan memberi skor jawaban Anda pada kasus uji sulit berikut yang mungkin menarik untuk diuji:
513231721363284898797712130584280850383: 40206835204840513073 12764787846358441471
Skor
Skor Anda adalah waktu gabungan untuk memperhitungkan semua kasus uji di atas dengan penalti 10 menit untuk setiap faktorisasi yang gagal (semua dibulatkan ke detik terdekat). Kode Anda juga harus bekerja untuk bilangan bulat lain, yang seharusnya tidak hanya berupa kode jawaban ini.
Saya akan menghentikan kode Anda setelah 10 menit.
Jika dua orang mendapatkan skor yang sama maka jawaban pertama menang.
Batasan
Kode Anda tidak dapat menggunakan fungsi bawaan atau pustaka yang melakukan faktorisasi bilangan bulat. Anda dapat mengasumsikan input tersebut membutuhkan kurang dari 256 bit. Semua angka input akan menjadi gabungan.
Bagaimana saya akan mengatur waktu?
Saya benar-benar akan berjalan time ./myprog
di sistem Ubuntu saya untuk melakukan pengaturan waktu jadi tolong sediakan juga program lengkap untuk saya jalankan yang mencakup fungsi apa pun yang telah Anda tetapkan.
Catatan untuk bahasa yang dikompilasi
Waktu kompilasi harus tidak lebih dari 1 menit pada mesin saya.
Apakah ini mungkin?
Jika Anda mengabaikan batasan ruang, maka masing-masing dapat diperhitungkan dalam waktu kurang dari 2 detik di komputer saya menggunakan kode Python murni + pypy.
Jadi apa yang dimaksud dengan algoritma pemfaktoran non-sepele?
Algoritma rho Pollard cepat dan cocok untuk bermain golf. Tentu saja ada banyak cara lain untuk faktor bilangan bulat juga.
Yang lebih cepat lagi adalah saringan Quadratic . Sepertinya tantangan serius untuk memerasnya menjadi 140 byte.
Skor terkemuka
- SEJPM , penalti 10 menit untuk kasus uji terakhir + 16 detik di Haskell
2 ** 1024
?2
atau2, 2
?Jawaban:
Haskell,
100979189877267 BytesCobalah secara Online!
-3 byte terima kasih kepada @flawr
-6 byte terima kasih kepada @flawr lagi
-2 byte terima kasih kepada @flawr lagi
-2 byte berkat set parameter yang dioptimalkan
-1 byte berkat @flawrs waktu lain
-14 byte berkat persyaratan untuk hanya mengeluarkan satu faktor
-5 byte berkat @AndersKaseorg
Ini berfungsi untuk 5 kasus uji pertama dalam waktu yang tidak diketahui.
Ini mungkin akan time-out pada test case terbesar.
Secara umum ini biasanya akan mengembalikan satu faktor non-sepele dalam waktu sebanding dengan akar kuadrat dari faktor terkecil.
Ini tidak akan bekerja pada setiap input karena tidak bervariasi polinomial dan deteksi kasus luar biasa sulit dilakukan dalam 140 byte.
Ini juga tidak akan menghasilkan faktorisasi penuh, melainkan faktor non-sepele dan pembagian input oleh faktor ini.
Ini juga tidak akan mengurutkan faktor berdasarkan ukuran.
Metode yang digunakan adalah Pollard-Rho-Factoring dengan nilai awal standar 2 (dengan
x^2+1
polinom standar diterapkan satu kali) dan faktor konstanta polinomial non-standar 7 (karena1
tidak bekerja dengan 1679) untuk semua evaluasi lebih lanjut.Program lengkap (
factor.hs
):Kompilasi sebagai
$ ghc factor.hs
(perlughc
diinstal).Jalankan sebagai
$ ./factor <number>
.Contoh dijalankan:
Kode tidak dikunci:
Menghitung faktor non-sepele dengan menelepon
g
dengan nilai awal. Polinomial diterapkan sebelumnya pada 2 di sini dan diterapkan kembali pada hasil (5) sehingga input keg
(dalam klausa "di mana" ) selalu dapat dengan mudah digunakan untuk uji-gcd.g
(versi golf menggunakan infix#
) kemudian mencoba menghitung faktor non-sepeled
(di mana klausa dalam versi un-golf, in-line dalam yang golf) sebagai perbedaan antara dua inputg
, jika berhasil mengembalikan faktor tersebut , coba lagi. Di sini ia dapat menghasilkann
sebagai output jikaa==b
dan dengan demikian hanya mengembalikan faktor sepele, pendekatan yang tepat untuk menangani ini adalah dengan memvariasikan nilai awal pada peristiwa ini atau mengubah polinomial.sumber
|1<2=s a#(s$s b)
dapat diganti dengan|c<-s b=s a#s c
saya pikir :) (juga: mengapa Anda tidak memposting tautan TIO ?)abs
, karenab
selalu tidak negatif. (Mungkin maksud Andaabs$b-a
, tetapigcd
menerima argumen negatif dan selalu menghasilkan hasil yang tidak negatif.) Itu membuat ini menjadi kurang dari setengah tweet!Pari / GP , 137 byte, ~ 5 detik
Menggunakan operasi kurva elips bawaan GP (dan beberapa penyetelan parameter curang) :
ecm
adalah fungsi yang (harus) mengembalikan faktor. Cobalah online!Uji:
Tidak Disatukan:
Sayangnya, penanganan faktor 2 dan 3 menggunakan banyak byte. Bytes yang bisa digunakan untuk menambah tahap 2:
sumber
Aksioma, 137 byte 9 menit
di atas fungsi p () yang akan mengimplementasikan p-1 algo untuk anjak di bawah ini apa yang akan disalin dalam file untuk pengujian pada fungsi p ()
hasil di sini:
sumber
Aksioma, 10 menit + 31 detik
z () adalah fungsi rho, satu fungsi 137 byte; ungolfed z () dan menyebutnya sebagai rho (). Itu akan mengira bahwa gcd (0, n) = n sehingga loop berhenti dan kembali untuk gagal n.
hasil (z () tidak apa-apa kecuali angka terakhir 1751952685614616185916001760791655006749 tetap tidak diperhitungkan (10 menit))
sumber
Python 3 ,
10099 byte,45 4039 detik + penalti 10 menitCobalah online!
Menggunakan Pollard-Rho dengan nilai awal 2 dan polinomial x ^ 2 +1.
sumber
pow
(dengan argumen ke-3) untuk meningkatkan kecepatan eksekusi Anda.