"Katak utama" adalah hewan aneh yang melompat di antara bilangan bulat, sampai tiba pada 3 atau 19 ...
Program Anda harus menerima bilangan bulat n
sebagai input dan output hasil dari algoritma di bawah ini ( 3
atau 19
).
Untuk bilangan bulat yang diberikan n >= 2
:
- Biarlah
f
posisi katak. Awalnya diatur ken
- jika
f = 3
atauf = 19
: katak berhenti melompat - hentikan program dan outputf
. - if
f
is prime: katak melompat ke posisi2×f-1
. Kembali ke langkah 2. - jika
f
komposit: marid
menjadif
pembagi utama terbesar. Katak melompat ke posisif-d
. Kembali ke langkah 2.
Contoh:
Contoh dengan n = 5
:
5 > 9 > 6 > 3 stop
Program harus menampilkan 3
.
Contoh lain dengan n = 23
:
23 > 45 > 40 > 35 > 28 > 21 > 14 > 7 > 13 > 25 > 20 > 15 > 10 > 5 > 9 > 6 > 3 stop
Sekali lagi, program harus menampilkan 3
.
Kasus uji:
10 => 3
74 => 19
94 => 3
417 => 3
991 => 19
9983 => 19
Anda dapat mengasumsikan 1 < n < 1000000
(saya telah memeriksa akhir program untuk nilai-nilai ini).
3
atau19
, kita dapat mengubah item 2. dalam algoritma untuk mengatakan bahwa jika katak telah memasuki loop apa pun (menemukan posisi yang telah dilihatnya sebelumnya), maka ia berhenti melompat dan mengembalikan yang terkecil. anggota dari loop itu.Jawaban:
Python 2 ,
101939290888785 byteCobalah online!
sumber
while~16&n!=3
menghemat satu byte.~16&n-3
bahkan berhasil!C (gcc),
8765 byteCobalah online!
Penjelasan:
Versi portabel (72 byte):
Cobalah online!
Dengan nama variabel yang lebih tepat:
Cobalah online!
sumber
Retina ,
6362 byteTerima kasih kepada Neil untuk menghemat 1 byte.
Cobalah online!
Input dan output dalam unary (test suite menggunakan desimal untuk kenyamanan). Solusi ini menjadi sangat lambat untuk input yang lebih besar. Waktu
9983
ujian habis pada TIO.Penjelasan
Karena itu
{
, kedua tahap program hanya dijalankan dalam satu lingkaran sampai mereka tidak lagi mempengaruhi string. Kami bergantian antara komposit pemrosesan panggung dan bilangan prima pemrosesan panggung. Itu memungkinkan kita menghindari persyaratan yang sebenarnya (yang tidak benar-benar ada di Retina). Jika nilai saat ini adalah jenis yang salah untuk panggung, panggung tidak melakukan apa-apa.Ini memproses komposit. Kami cocok dengan pembagi potensial dengan
(11+)
, tetapi kemudian kami memeriksa bahwa itu tidak komposit dengan(?<!^\2+(11+))
, jadi kami hanya mempertimbangkan faktor prima. Karena keserakahan+
, ini memprioritaskan faktor terbesar. Kemudian kami memeriksa bahwa pembagi potensial ini adalah pembagi yang sebenarnya dengan mencoba mencocokkan sisa string dengan pengulangan(?=\1+$)
,. Pembagi ini hanya dihapus dari string, yang merupakan cara Anda mengurangi sesuatu secara unary.Ini memproses bilangan prima, kecuali 3 dan 19 . Lookahead negatif memastikan bahwa input tidak komposit, bukan 3 dan bukan 19 . Kemudian kami mencocokkan satu
1
dan menggantinya dengan seluruh string. Ini adalah bentuk unary komputasi n - 1 + n , yang tentu saja adalah 2n-1 .Setelah kami menekan 3 atau 19 , kedua panggung tidak dapat mencocokkan string dan itu tidak akan lagi berubah.
sumber
1$'
sama dengan$_
?Sekam , 15 byte
Cobalah online!
Penjelasan
sumber
Jelly , 12 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Bahasa Wolfram (Mathematica) , 65
6668byteCobalah online!
Terinspirasi oleh tip . Pada dasarnya, itu hanya membuat ulang algoritma.
//.
adalahRepeatedReplace
dan/;
sekarangCondition
. Jadi, kode akan menggantikani_
(jumlah tunggal) denganIf[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]
, sampaii!=3&&!=19
mengevaluasiTrue
.Benchmark:
sumber
10000000010
karenamaximum number of iterations is 2^16 (= 65536)
#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&
05AB1E ,
191817 byteCobalah online!
Penjelasan
sumber
<ë
JavaScript (ES6),
737169 byteUji kasus
Tampilkan cuplikan kode
Diformat dan dikomentari
sumber
57%n
dann%38
bukannyan==3|n==19
. Disimpan 1 byte dalam jawaban Java saya juga, jadi terima kasih!Jelly ,
2319 byte-4 byte dari mil . Masih lebih lama dari 05AB1E.
Cobalah online!
sumber
Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿
menggunakan loop sementara sebagai gantinya dan beberapa pemesanan ulangPython 2 ,
110105103101 byte-2 byte terima kasih kepada @Lynn
Cobalah online!
Python 2 ,
116112105 byteCobalah online!
sumber
…n*(n&~16==3)or…
menghemat 2 byte.MATL ,
2221 byteTerima kasih kepada @Giuseppe karena menghapus 1 byte!
Cobalah online! Atau verifikasi semua kasus uji .
Penjelasan
sumber
Haskell - 154 byte
Mungkin melewatkan beberapa trik golf di sini, ini adalah usaha pertama saya di haskell golf.
sumber
1>0
untukTrue
sebagian besar kali tetapi sering mungkin lebih baik untuk menggunakan sebuah tugas, misalnyac<-z n
.[x|x<-[b-1,b-2..1],rem b x==0]
juga pendek darireverse[x|x<-[1..(b-1)],b
remx==0]
.Neim ,
1716 bytePenjelasan:
Cobalah online!
sumber
Angka R + ,
10299 byteCobalah online!
R tidak dikenal dengan built-in pendek, dan bahkan paket pun mengikutinya!
sumber
Java 8,
14013513494 byte-5 byte mengkonversi metode Java 7 rekursif ke Java 8 lambda dengan loop.
-1 byte secara implisit berkat jawaban JavaScript @Arnauld dengan mengubah
n!=3&n!=19
danreturn n;
ke57%n>0
danreturn n%38;
.Saya pikir itu mungkin untuk menggabungkan kedua loop dan memeriksa apakahn
itu prima, dan mendapatkan faktor prima terbesar pada saat yang sama, tetapi saya belum bisa mengetahuinya (belum). Jadi ini akan menjadi versi awal untuk saat ini.-40 byte kekalahan berkat @Nevay, dengan melakukan apa yang tidak bisa saya lakukan: menggabungkan loop untuk memeriksa bilangan prima dan faktor prima terbesar sekaligus.
Penjelasan:
Cobalah di sini (jalankan bahkan
999999
dalam waktu kurang dari 1 detik).sumber
n=>
bukannyan->
. Dan terkadang panggilan huruf kecil / besar. ;)n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;)t/=m=f;return n%38;}
Bash, 73 byte
Cobalah online! Dimodifikasi sedikit agar bekerja di TIO.
Secara rekursif memanggil file skrip sendiri menggunakan
$0
,yang tidak berfungsi di TIO karena harus dijalankan sebagai. Menerima input sebagai argumen baris perintah../filename.sh
Menggunakan trik modulus yang sama dengan jawaban JS @ Arnauld .
Uji Kasus
sumber
Python 3 , 97 byte
Cobalah online!
sumber
Pyth , 19 byte
Verifikasi semua kasus uji!
The Husk jawaban mengilhami saya untuk menyimpan 2 bytes (
,3 19
untukP57
).Bagaimana ini bekerja?
sumber
PowerShell ,
150126 byteCobalah online! (peringatan: lambat untuk jumlah yang lebih besar)
Metode berulang. PowerShell tidak memiliki built-in faktorisasi prima, jadi ini meminjam kode dari jawaban saya pada Prime Factors Buddies .
Pertama adalah
for
loop kami . Pengaturan ditetapkan$n
sebagai nilai input, dan kondisi membuat loop tetap selama57%$n
tidak nol (terima kasih kepada Arnauld untuk trik itu). Di dalam loop pertama-tama kita mendapatkan daftar faktor prima$a
(diatur ke$n
). Ini adalah kode yang dipinjam dari Prime Factors Buddies. Jika input$a
sudah prima, ini akan kembali hanya$a
(penting nanti). Itu (berpotensi adil$a
) disimpan ke dalam$d
.Berikutnya adalah
if
/else
kondisional. Untukif
bagian itu, kami memeriksa apakah$n
ada-in
$d
. Jika ya, itu berarti yang$n
utama, jadi kita ambil$n=2*$n-1
atau$n+=$n-1
. Kalau tidak, itu komposit, jadi kita perlu menemukan faktor prima terbesar. Itu berarti kita perlu mengambil yang terakhir[-1]
dari$d
dan kurangi yang dari$n
dengan$n-=
. Ini berfungsi karena kita beralih dari2
dan dengan demikian elemen terakhir$d
sudah akan menjadi yang terbesar.Setelah kami selesai mengulang, kami hanya menempatkan
$n%38
(sekali lagi, terima kasih Arnauld) pada pipeline dan output tersirat.sumber
APL (Dyalog Unicode) ,
1139059 byteCobalah online!
TIO bekerja dengan nilai hingga ~ 3200. Diuji pada PC saya untuk test case terakhir. Untuk mengujinya di TIO, cukup tambahkanTidak berlaku lagi, terima kasih kepada @ Adám karena telah menunjukkan bahwa algoritma pemeriksaan keaslian saya benar-benar buruk dan memberi saya pengganti; juga untuk menghemat 23 byte.f value
ke bagian bawah kode.Diedit untuk memperbaiki jumlah byte.
Bagaimana itu bekerja
sumber
Aksioma, 93 byte
uji:
Akan ada fungsi 68 byte
tetapi untuk n = 57991 (jika saya ingat dengan baik) itu keluar dari ruang stack dicadangkan.
sumber
Python 2 , 93 byte
Port dari jawaban TFeld tanpa lib eksternal.
Cobalah online!
sumber