Tantangan ini cukup sederhana bahwa pada dasarnya semua dalam judul: Anda diberi positif bilangan bulat N dan Anda harus kembali bilangan bulat positif terkecil yang bukan merupakan pembagi dari N .
Contoh: pembagi N = 24 adalah 1, 2, 3, 4, 6, 8, 12, 24
. Bilangan bulat positif terkecil yang tidak ada dalam daftar itu adalah 5 , jadi itulah hasil solusi Anda.
Ini adalah urutan OEIS A007978 .
Aturan
Anda dapat menulis program atau fungsi dan menggunakan salah satu metode standar kami untuk menerima input dan memberikan output.
Anda dapat menggunakan bahasa pemrograman apa pun , tetapi perhatikan bahwa celah ini dilarang secara default.
Ini adalah kode-golf , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.
Uji Kasus
100 istilah pertama adalah:
2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2,
3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3,
2, 3, 2, 4, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2,
3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3
Khususnya, pastikan jawaban Anda berfungsi untuk input 1 dan 2 yang hasilnya lebih besar dari input.
Dan untuk beberapa kasus uji yang lebih besar:
N f(N)
1234567 2
12252240 19
232792560 23
sumber
Jawaban:
Mathematica, 19 byte (pengkodean UTF-8)
Fungsi tanpa nama mengambil argumen integer nol dan mengembalikan integer positif. Bilah vertikal sekitar setengah jalan sebenarnya adalah karakter tiga byte U + 2223, yang menunjukkan hubungan yang dapat dibagi dalam Mathematica. Penjelasan:
Diedit untuk menambahkan: ngenisis menunjukkan bahwa
//.
, secara default, akan mengulang maksimal 65536 kali. Jadi implementasi ini bekerja untuk semua bilangan input yang kurang dari kelipatan bilangan bulat paling umum dari 1 hingga 65538 (khususnya, pada semua angka dengan paling banyak 28436 digit), tetapi secara teknis tidak untuk semua angka. Seseorang dapat menggantix//.y
denganReplaceRepeated[x,y,MaxIterations->∞]
untuk memperbaiki kekurangan ini, tetapi jelas dengan biaya 34 byte tambahan.sumber
For
,While
, dllPyth, 3 byte
Pada dasarnya,
f
loop kode sampai%QT
(diQ % T
manaT
variabel iterasi) benar.Cobalah online di sini.
sumber
.V1In%Qb0bB
Melihat jawaban Anda, dan tidak merasa begitu luar biasa lagi.JavaScript (ES6),
2523 byteCatatan: Satu hal yang menarik di sini adalah bahwa
k
parameter diinisialisasi ex nihilo pada iterasi pertama. Ini bekerja karenan % undefined
merupakanNaN
(falsy seperti yang diharapkan) dan-~undefined
sederajat1
. Pada iterasi berikutnya,-~k
pada dasarnya setara dengank+1
.Uji
Tampilkan cuplikan kode
sumber
Python,
433635 bytesumber
Hexagony , 12 byte
Diwarnai:
Cobalah online!
sumber
R, 28 byte
Cukup mudah, tidak ada yang mewah. Mengambil input dari stdin, nilai kenaikan
T
hinggai
moduloT
bukan nol.Jika Anda menginginkan sesuatu yang sedikit lebih mewah, berikut ini ada 29 byte :
Dijelaskan:
sumber
which.min
, tetapi kemudian saya melihat hasil edit dan sepertinyamatch
melakukan pekerjaan yang serupa.T
, menyimpan kebutuhan untuk mendefinisikannya sebelumwhile
loop.while
pendekatan, yang bagus karena sangat intensif memori untuk N. besar.T
Triknya adalah salah satu suguhan yang bagus untuk bermain golf tetapi benar-benar mengerikan untuk pemrograman yang sebenarnya. (Dan tentu saja Anda dapat menggunakanF
juga saat Anda membutuhkan0
.)%%
lebih diutamakan+
, jadi parens masih diperlukan:,(0:i+1)
dengan jumlah byte yang sama dengan1:(i+1)
. Saya sebenarnya memiliki yang pertama, tetapi mengubahnya ke yang terakhir karena lebih mudah dibaca.Haskell, 26 byte
Semua orang lupa tentang
until
!sumber
Brachylog , 10 byte
Cobalah online!
Ini keluar sangat mirip dengan (tetapi lebih pendek dari) solusi asli Fatalize. Sejak itu Fatalize telah beralih ke algoritme lain yang terkait dengan ini melalui metode yang berbeda, jadi saya harus menjelaskannya sendiri:
Ketika kita membalikkan fungsi, dengan menukar "input" dan "output", kita mendapatkan algoritma yang cukup masuk akal (hanya dinyatakan dengan cara yang canggung): "coba kemungkinan bilangan bulat positif, dalam urutan alami mereka (yaitu 1 ke atas), sampai Anda menemukan yang tidak dapat dikalikan dengan apa pun untuk menghasilkan input ". Brachylog tidak melakukan perhitungan titik-mengambang kecuali semua input diketahui, sehingga hanya akan mempertimbangkan integer A.
sumber
Brachylog ,
1110 byteCobalah online!
Penjelasan
sumber
SAPI, 174 byte
Cobalah online!
Kode ini hanya sebagian milik saya sendiri - ini mengimplementasikan algoritma modulus yang saya porting dari brainfuck. Sisa kode adalah milik saya. Namun, karena saya tidak menulis algoritma modulus, saya belum benar-benar menyelidiki cara kerjanya dan tidak dapat mendokumentasikan bagian kode tersebut. Sebagai gantinya, saya akan memberikan uraian yang biasa, diikuti dengan penjelasan yang lebih mendalam tentang mengapa kode itu bekerja.
Rincian kode
Penjelasan
Kode pertama kali membaca bilangan bulat ke [0]. Setiap iterasi dari loop utama (baris 2 hingga 26) bertambah [1], kemudian menyalin semua yang diperlukan ke algoritma modulus, yang memuntahkan hasilnya ke [5]. Jika [5] berisi nilai apa pun, maka [1] adalah angka yang perlu kita cetak. Kami mencetaknya, dan kemudian secara paksa keluar dari program.
Karena COW adalah turunan dari brainfuck, fungsinya relatif mirip dengan cara brainfuck beroperasi - strip pita tanpa batas, Anda dapat bergerak ke kiri atau ke kanan, menambah atau mengurangi, dan "memutar" sementara nilai pita saat ini adalah nol. Selain brainfuck, SAP dilengkapi dengan beberapa fitur yang bermanfaat.
Poin nyata yang menarik di sini adalah instruksi 3
mOO
,. Interpreter membaca nilai rekaman saat ini, dan menjalankan instruksi berdasarkan nilai rekaman itu. Jika nilainya kurang dari 0, lebih besar dari 11, atau sama dengan 3, juru bahasa mengakhiri program. Kita dapat menggunakan ini sebagai kekuatan cepat dan kotor keluar dari loop utama (dan program sepenuhnya) setelah kami menemukan non-pembagi kami. Yang harus kita lakukan adalah mencetak nomor kita, hapus [1] (denganOOO
), kurangi menjadi -1 denganMOo
, dan kemudian jalankan instruksi -1 melaluimOO
yang mengakhiri program.Rekaman itu sendiri untuk program ini berfungsi sebagai berikut:
Algoritma modulus membersihkan secara alami [2], [3], [6], dan [7] pada akhir operasi. Isi [4] ditimpa dengan register paste pada baris 4, dan [5] adalah nol ketika [0] habis dibagi oleh [1], jadi kita tidak harus menghapusnya. Jika [5] tidak nol, kami berhenti secara paksa pada saluran 23 sehingga kami tidak perlu khawatir.
sumber
05AB1E , 7 byte
Cobalah online!
Penjelasan
sumber
Jelly , 5 byte
Cobalah online!
Penjelasan:
Ini merupakan penyalahgunaan yang mengerikan dari
#
; ada banyak operator dalam program ini, tetapi satu ton operan yang hilang.#
benar-benar ingin1
diberikan secara eksplisit untuk beberapa alasan (jika tidak mencoba untuk default ke input); namun, semua hal lain yang tidak ditentukan dalam program default ke input program. (Jadi misalnya, jika Anda memberi 24 sebagai input, program ini menemukan 24 angka pertama yang tidak membagi 24, lalu mengembalikan yang pertama; jenis pemborosan, tetapi berhasil.)sumber
2%@1#
C,
3235 byteEdit: ditambahkan
i=1
di loopPemakaian
Versi Program Lengkap, 64 Bytes:
sumber
C #,
3937 byteDisimpan dua byte berkat Martin!
sumber
Perl, 19 byte
18 byte kode +
-p
bendera.Untuk menjalankannya:
Penjelasan yang tidak terlalu terperinci :
-
$.
adalah variabel khusus yang nilai defaultnya adalah nomor baris saat ini dari filehandle terakhir yang diakses (stdin di sini), jadi setelah membaca input baris pertama, disetel ke 1.-
$_
menyimpan input dan dicetak secara implisit di akhir (terima kasih untuk-p
bendera).-
redo
(dalam konteks itu) menganggap bahwa program dalam satu lingkaran dan mengulangi iterasi saat ini (hanya$.
akan berbeda karena bertambah).- Jadi, jika kami menemukan nomor terkecil (tersimpan di
$.
) yang tidak dibagi$_
, maka kami mengaturnya$_
, jika tidak, kami mencoba nomor berikutnya (terima kasihredo
).sumber
Oktaf / MATLAB,
2624 bytefind(...,1)
mengembalikan indeks (1
-based) elemen bukan nol pertama dari vektor dalam argumen pertama. Argumen pertama adalah[n mod 1, n mod 2, n mod 3, n mod 4,...,n mod (n+1)]
Itu berarti kita harus menambah+1
indeks, karena kita mulai menguji pada1
. Terima kasih @Giuseppe untuk -2 byte.Cobalah online!
sumber
@(n)find(mod(n,1:n+1),1)
lebih pendek, bukan?Jelly , 6 byte
Cobalah online!
Penjelasan:
sumber
[1, 1, 1, 1, 5, ...]
.Perl 6 , 17 byte
Cobalah
Diperluas:
sumber
05AB1E , 6 byte
Cobalah online!
Juga, itu mengeja "LINK!" ... Agak ...
sumber
Jelly , 5 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Python 2.7.9, 32 byte
Uji Ideone
Secara rekursif menghitung potensial non-pembagi
d
. Lebih pendek untuk meningkatkan hasil secara rekursi daripada outputd
. Offset1
diraih oleh Boolean ofTrue
, yang sama dengan1
, tetapi karenad==1
selalu merupakan pembagi, output selalu dikonversi ke angka.Python 2.7.9 digunakan untuk mengizinkan
0or
. Versi mulai 2.7.10 akan mencoba untuk menguraikan0or
sebagai awal dari angka oktal dan diberi kesalahan sintaksis. Lihat ini di Ideone .sumber
Sebenarnya , 7 byte
Cobalah online! (catatan: ini adalah solusi yang sangat lambat, dan akan memakan waktu lama untuk kasus uji besar)
Penjelasan:
sumber
Haskell , 29 byte
Ekspresi
[k|k<-[2..]]
hanya membuat daftar tak terbatas[2,3,4,5,...]
. Dengan kondisi tersebutmod n k>0
kami hanya mengizinkan mereka yang adak
di daftar yang tidak membagin
. Menambahkan!!0
hanya mengembalikan entri pertama (entri pada indeks0
) dari daftar itu.Cobalah online!
sumber
Dyalog APL , 8 byte
1⍳⍨
posisi True pertama di0≠
nilai bukan nol dari⍳|
sisa pembagian 1 ... N bila dibagi dengan⊢
NTryAPL online!
Catatan: ini berfungsi untuk 1 dan 2 karena
1⍳⍨
mengembalikan 1 + panjang argumennya jika tidak ada yang ditemukan.sumber
julia, 28 byte
Catatan: karena
1:N+2
tidak mengalokasikan memori, tidak ada masalah memori untukN
s- @flawr besar ,
N+2
simpan untuk saya beberapa byte- Saran @Martin disimpan 1 byte
sumber
QBIC , 14 byte
Penjelasan:
sumber
PHP, 30 byte
jika dijalankan dari konsol dengan
-r
opsi (thx ke @ ais523)32 byte
terima kasih kepada @manatwork untuk menghapus 1 byte
33 byte (asli)
sumber
<?
tidak harus menjadi bagian dari jumlah byte Anda (karena PHP memiliki mode baris perintah yang tidak memerlukannya).<1
bukan==0
.for(;!($argv[1]%$i);$i++);echo$i;
. Milikmu adalah evolusi alami milikku. Ini yang saya dapatkan!Cubix ,
1412 byteDisimpan 2 byte berkat MickyT.
Cobalah
Penjelasan
Dalam bentuk kubus, kodenya adalah:
Pada dasarnya, ini hanya mengambil input dan memulai penghitung. Kemudian memeriksa setiap nilai konter berturut-turut sampai menemukan nilai yang bukan merupakan faktor input.
sumber
I2/L/);?%<@O
untuk beberapa byte lebih sedikit. Proses umum yang sama, jalan yang berbeda> <> , 15 +3 = 18 byte
Input diharapkan berada di stack saat program dimulai, jadi +3 byte untuk
-v
flag. Cobalah online!sumber
Ubur-ubur ,
1210 byteMengambil input dari STDIN dan output ke STDOUT. Cobalah online!
Martin Ender menyimpan 2 byte, terima kasih!
Penjelasan
Bagian ini adalah salah satu fungsi yang menggunakan nilai input dalam definisinya.
Ini
~
-cell diberikan fungsi, sehingga membalik argumen: nya menghasilkan fungsi biner "argumen kiri Modulo (|
) argumen yang tepat". Fungsi modulo bawaan di Jellyfish mengambil argumennya dalam urutan terbalik.Ini
~
-cell diberi nilai dan fungsi, sehingga tidak aplikasi parsial: menghasilkan fungsi biner "input (i
) modulo argumen yang tepat". Sebut saja fungsi itu f .The
\
-cell diberikan dua fungsi, sehingga tidak iterasi: menghasilkan fungsi unary "increment (>
) sampai fungsi f diterapkan untuk nilai-nilai sebelumnya dan saat ini memberikan truthy (nol) hasil, kemudian kembali nilai saat ini". Ini berarti bahwa argumen bertambah hingga tidak membagi input.Akhirnya, kami menerapkan fungsi ini ke nilai awal
1
dan mencetak hasilnya denganp
.sumber