"Semut utama" adalah hewan keras kepala yang menavigasi bilangan bulat dan membaginya sampai hanya tersisa bilangan prima!
Awalnya, kami memiliki array tak terbatas A yang berisi semua bilangan bulat> = 2: [2,3,4,5,6,.. ]
Membiarkan p
menjadi posisi semut pada array. Mulanya,p = 0
(array diindeks 0)
Setiap belokan, semut akan bergerak sebagai berikut:
- jika
A[p]
prima, semut bergerak ke posisi berikutnya:p ← p+1
- lain, jika
A[p]
adalah bilangan komposit, biarkanq
menjadi pembagi yang lebih kecil> 1. Kami membagiA[p]
olehq
, dan kami tambahkanq
untukA[p-1]
. Semut bergerak ke posisi sebelumnya:p ← p-1
Inilah langkah pertama untuk semut:
2 3 4 5 6 7 8 9 ...
^
2 3 4 5 6 7 8 9 ...
^
2 3 4 5 6 7 8 9 ...
^
2 5 2 5 6 7 8 9 ...
^
2 5 2 5 6 7 8 9 ...
^
2 5 2 5 6 7 8 9 ...
^
2 5 2 5 6 7 8 9 ...
^
2 5 2 7 3 7 8 9 ...
^
Program Anda harus menampilkan posisi semut setelah n
bergerak. (Anda bisa berasumsi n <= 10000
)
Kasus uji:
0 => 0
10 => 6
47 => 9
4734 => 274
10000 => 512
Sunting. Anda juga dapat menggunakan daftar yang diindeks 1, dapat diterima untuk menampilkan hasil 1, 7, 10, 275, 513 untuk test case di atas.
Ini adalah kode-golf, jadi kode dengan kode terpendek dalam byte akan menang.
n
(atau apakah case komposit bisa mendorong semut ke kiri inisial2
).1,7,10,275,513
jika 1-pengindeksan dinyatakan? Atau apakah mereka masih harus mencocokkan output Anda.Jawaban:
Alice , 45 byte
Cobalah online!
Sebagian besar implementasi langsung.
n
Waktu Looping di Alice biasanya dilakukan dengan menekann-1
kali alamat kembali , kemudian kembali pada akhir setiap iterasi dengank
. Terakhir kali melalui loop,k
instruksi tidak punya tempat untuk kembali, dan eksekusi berlanjut.Program ini menggunakan
k
instruksi yang sama untuk berhenti lebih awal ketika nomornya prima. Akibatnya, iterasi terakhir akan selalu menggerakkan semut ke kiri. Untuk mengimbangi bug ini, kami melakukann+1
iterasi pada larik 1-diindeks, yang memberikan hasil persis seperti yang kita inginkan (dan memberikan kasingn=0
gratis).sumber
Python 2 , 120 byte
Cobalah online!
Ah, langka
for
-else
lingkaran! Theelse
klausul hanya mengeksekusi jikafor
tubuh tidak keluar melaluibreak
. Dalam kasus kami, ini berarti kami memeriksa semuaq
dan tidak menemukan satupun dari mereka untuk dibagip
.sumber
Oktaf ,
109 103 10194 byteCobalah online!
Kode ini akan menampilkan posisi dalam pengindeksan 1, jadi output untuk kasus uji adalah:
Versi ini menggunakan beberapa optimisasi Oktaf sehingga tidak kompatibel dengan MATLAB. Kode di bawah ini adalah versi yang kompatibel dengan MATLAB.
MATLAB,
130 123 118117 byteMenggunakan pengindeksan 1 seperti pada versi Oktaf. Saya sudah mengujinya terhadap semua kasus uji di MATLAB. Sebagai contoh, output pada 100000 adalah 3675 (satu-pengindeksan).
Versi komentar dari kode di atas:
Yang menarik, ini adalah posisi semut vs jumlah iterasi untuk 10000 nilai pertama dari n.
Tampaknya Semut mungkin akan cenderung tak hingga, tetapi siapa tahu, penampilan bisa menipu.
for
alih - alihwhile
dan menghapus tanda kurung dariif
- Terima kasih @Giuseppe\=
dan+=
operasi - Terima kasih @Giuseppei++
dani--
- Terima kasih @LuisMendosumber
end
mencocokkan tanda tangan fungsiend
bersifat opsional.end
juga opsional dalam Oktaf. Ini hanya diperlukan karena Anda memiliki kode setelah fungsiJavaScript (ES6), 91 byte
Demo
NB: Anda mungkin harus menambah ukuran tumpukan standar mesin Anda agar bisa lulus semua test case.
Cobalah online!
sumber
Haskell ,
10810694 byteCobalah online! Contoh penggunaan:
([0]#[2..]!!) 10
hasil6
(diindeks 0).Fungsi
#
beroperasi pada dua daftar, bagian depan terbalik array[p-1, p-2, ..., 1]
dan sisa array yang tak terbatas[p, p+1, p+2, ...]
. Ini membangun daftar posisi yang tak terbatas, dari manan
posisi th dikembalikan diberi inputn
.Pola ini
((a:b)#(p:q))
mengikatp
nilai posisi semut saat ini dana
ke nilai posisi semut sebelumnya.b
adalah awalan dari array dari posisi 1 kep-2
danq
sisanya tak terbatas mulai dari posisip+1
.Kami membangun daftar panggilan rekursif dengan cara berikut: Kami melihat setiap pembagi
d
darip
(yang lebih besar dari satu dan lebih kecil darip
) dalam urutan menaik dan menambahkanb#(a+d:div p d:q)
untuk masing-masing, yaitu nilai saatp
ini dibagi olehd
dan bergerak semut satu langkah ke kiri tempatd
ditambahkana
. Kemudian kita tambahkan(p:a:b)#q
ke akhir daftar ini, yang menunjukkan semut bergerak satu langkah ke kanan.Kami kemudian mengambil panggilan rekursif pertama dari daftar dan menambahkan posisi saat ini, yang bertepatan dengan panjang daftar awalan
b
. Karena pembagi berada dalam urutan menaik, memilih yang pertama dari daftar panggilan rekursif memastikan kami menggunakan yang terkecil. Selain itu, karena(p:a:b)#q
ditambahkan ke akhir daftar, itu hanya dipilih jika tidak ada pembagi danp
dengan demikian prima.Suntingan:
-2 byte dengan mengalihkan daftar fungsi dari turun ke urutan naik.
-12 byte berkat ide Zgarb untuk mengindeks ke dalam daftar tanpa batas alih-alih menangani penghitung, dan dengan beralih ke pengindeksan 0.
sumber
TI-BASIC,
10810310298 byteInput dan output disimpan di
Ans
. Output diindeks 1.sumber
fPart(∟A(P)/F:
denganfPart(F¹∟A(P:
. Hal yang sama di baris berikutnya.not(fPart(7⁻¹7
adalah 0 tetapinot(fPart(7/7
1.MATL , 41 byte
Output berbasis 1. Waktu program habis untuk test case terakhir dalam juru bahasa online.
Cobalah online!
Penjelasan
Program menerapkan prosedur sebagaimana dijelaskan dalam tantangan. Untuk melakukannya, ia menggunakan clipboard manual dan otomatis MATL yang luar biasa berat.
Pembagi terkecil diperoleh sebagai entri pertama dalam dekomposisi faktor prima.
"Kesenjangan" update dilakukan oleh Timpa yang sesuai masuknya berbagai A . The "add" update dilakukan oleh unsur-bijaksana menambah Sebuah array yang berisi angka nol kecuali pada posisi yang diinginkan.
sumber
Pyth - 44 byte
Implementasi prosedur yang mudah.
Test Suite .
sumber
PARI / GP, 87 byte
Cukup jelas (tidak begitu golf-ish). Jika Anda tidak menghitung
f(n)=
bagian, itu adalah 82 byte. Anda juga dapat memulai dengann->
(85 byte).Ini adalah bahasa 1-diindeks.
Sunting: Modifikasi
illustrate(n,m)=A=[2..m+1];p=1;for(i=1,n,for(j=1,m,printf("%5s",if(j==p,Str(">",A[j],"<"),Str(A[j]," "))));print();q=factor(A[p])[1,1];if(A[p]!=q,A[p]/=q;p--;A[p]+=q,p++))
akan mencetak ilustrasi jalan semut (diberi terminal yang cukup lebar). Misalnyaillustrate(150,25)
akan memberikan 150 langkah pertama pada 25 kolom, seperti ini:sumber
Python 2 ,
142127 byteCobalah online!
sumber
P(n)
n<=4
Mathematica,
118103 byteCobalah online!
Martin Ender menyimpan 15 byte
sumber
Divisors
, Anda dapat menggunakan notasi infiks untukDo
, dan Anda bisa kembalit
sebagai gantinyat-1
(hasil berbasis 1).Python 3 ,
158149133 byteIni adalah implementasi prosedural langsung dengan satu atau dua kebiasaan untuk memastikan kode bekerja untuk semua kasus uji. Saya menggunakan
[*range(2,n+9)]
untuk memastikan bahwa A cukup besar (kecuali untukn<3
,n+9
lebih dari cukup). Theelse
klausul membagi tuaA[p]
olehd
, decrementsp
, dan kemudian menambahkand
ke baruA[p]
, yang pasti praktek coding yang buruk. Kalau tidak, cukup mudah. Selamat datang saran bermain golf!Sunting: -9 byte tanpa
sympy
terima kasih kepada Halvard Hummel. -14 byte dari Felipe Nardi Batista, -6 byte dari beberapa isyarat dari jawaban Jonathan Frech's Python 2Cobalah online!
sumber
if d-m:A[p]...
danelse:p+=1
untuk menyimpan byteelse
pernyataanelse
pernyataan tersebut, tidak ada perbedaan dalam byte ke versi fungsiPHP, 102 +1 byte
Jalankan sebagai pipa dengan
-R
atau coba online .Output kosong untuk input
0
; masukkan+
setelahecho
untuk literal0
atau gunakan versi 1-diindeks ini (103 + 1 byte):
sumber
R , 123 byte
Implementasi yang mudah. Ini disediakan sebagai fungsi, yang mengambil jumlah gerakan sebagai input dan mengembalikan posisi p.
Itu loop di atas urutan dan bergerak penunjuk maju dan mundur sesuai dengan aturan. Outputnya berbasis 0.
Catatan: untuk menemukan faktor prima terkecil dari bilangan x, ia menghitung modulus x relatif terhadap semua bilangan bulat dari 0 hingga x. Kemudian ekstrak angka-angka dengan modulus sama dengan 0, yang selalu [0,1, ..., x]. Jika angka ketiga tersebut bukan x, maka itu adalah faktor prima terkecil dari x.
Cobalah online!
sumber
C (gcc),
152148 byteDiperkecil
Dibentuk dengan beberapa komentar
Fungsi utama untuk pengujian
Untuk menunjukkan setiap langkah
Deklarasikan tampilan () di dalam f ()
Tampilan panggilan ()
Tampilan panggilan ()
sumber
Clojure, 185 byte
Aduh, mengedit "keadaan" tidak ideal di Clojure. Anda harus meningkatkan eksponen untuk input yang lebih besar.
sumber
loop
? Anda harus dapat kehilangan beberapa byte tanpa itu.first
hal itu menjadisome
pernyataan.recur
dua kali, satu untuk setiapif-let
cabang. Juga(dec i)
akan diduplikasi.some
butuh predikat, saya bisa menggunakan+
karena kita berurusan dengan angka tetapi ini adalah satu karakter lebih lama darifirst
. CMIIWJava 8,
138135 bytePenjelasan:
Coba di sini.
sumber
Clojure,
198193191 byteIni harus sangat golf ...
Golf 1 : Disimpan 5 byte dengan mengubah
(first(filter ...))
ke(some ...)
Golf 2 : Disimpan 2 byte dengan mengubah
(zero? ...)
ke(= ... 0)
Pemakaian:
Kode tidak dikunci:
sumber