Dari semua tahun saya membuat tantangan ini, 2017 adalah tahun pertama yang menjadi bilangan prima. Jadi pertanyaannya adalah tentang bilangan prima dan propertinya.
Tugas Anda adalah untuk menghasilkan program atau fungsi yang akan mengambil bilangan bulat positif besar yang sewenang-wenang sebagai input, dan menghasilkan atau mengembalikan apakah jumlahnya friable 2.017 - artinya, apakah faktor utama terbesar dalam jumlah itu adalah 2.017 atau kurang.
Beberapa contoh input dan outputnya:
1 (has no prime factors)
true
2 (= 2)
true
80 (= 2 x 2 x 2 x 2 x 5)
true
2017 (= 2017)
true
2019 (= 3 x 673)
true
2027 (= 2027)
false
11111 (= 41 x 271)
true
45183 (= 3 x 15061)
false
102349 (= 13 x 7873)
false
999999 (= 3 x 3 x 3 x 7 x 11 x 13 x 37)
true
1234567 (= 127 x 9721)
false
4068289 (= 2017 x 2017)
true
Program Anda tidak harus benar-benar menampilkan true
dan false
- nilai-nilai yang benar atau salah, dan pada kenyataannya setiap dua keluaran berbeda yang konsisten di seluruh kasus benar dan salah baik-baik saja.
Namun, Anda tidak boleh menggunakan bilangan prima dalam kode sumber Anda. Primes datang dalam dua jenis:
Karakter, atau urutan karakter, yang mewakili literal bilangan prima.
Karakter
2
,3
,5
, dan7
adalah ilegal dalam bahasa mana jumlahnya token valid.Angka
141
itu ilegal karena mengandung41
, meskipun1
dan4
sebaliknya valid.Karakter
B
danD
(ataub
dand
) ilegal dalam bahasa di mana mereka biasanya digunakan sebagai 11 dan 13, seperti CJam atau Befunge.
Karakter yang memiliki nilai Unicode bernilai prima, atau berisi byte bernilai prima dalam penyandiannya.
Karakter
%)+/5;=CGIOSYaegkmq
tersebut ilegal di ASCII, serta karakter carriage return.Karakter
ó
ini ilegal di UTF-8 karena penyandiannya ada0xb3
di dalamnya. Namun, dalam ISO-8859-1, penyandiannya sederhana0xf3
, yang komposit dan karenanya oke.
Kode terpendek untuk melakukan hal di atas dalam bahasa apa pun menang.
=
aturan bahasa standar yang paling ...Jawaban:
Jelly , 8 byte
Cobalah online! Perhatikan bahwa test case 11111 dan di atasnya agak terlalu banyak untuk TIO.
Verifikasi
Test case 999999 telah berjalan selama 13 jam. Saya pesimis tentang komputasi 2025! 4068289 ...
Bagaimana itu bekerja
sumber
(2^n)!
. Ini juga berlaku untuk input berukuran enam, tetapi setidaknya input berada dalam alfabet desimal daripada yang biner.Jelly , 8 karakter, 14 byte UTF-8
Cobalah online!
Jelly biasanya menggunakan codepage sendiri untuk program. Namun, sebagian besar builtin terkait prima dimulai dengan
Æ
, yaitu codepoint 13; tidak terlalu membantu. Untungnya, penerjemah juga mendukung UTF-8, yang memiliki penyandian yang lebih ramah.Verifikasi
Program ini, di UTF-8, hexdumps seperti ini:
Verifikasi bahwa semua byte adalah komposit:
Verifikasi bahwa semua titik kode Unicode adalah komposit:
Satu-satunya token yang diuraikan sebagai angka adalah
90
. Tak satu pun dari9
,,0
dan90
prima.Penjelasan
Wawasan matematika utama di sini adalah bahwa 45² adalah 2025, yang jatuh dengan rapi antara 2017 (tahun berjalan) dan 2027 (perdana berikutnya). Dengan demikian, kita dapat mengambil akar kuadrat dari setiap faktor prima dari angka tersebut, dan melihat apakah ada yang melebihi 45. Sayangnya, kita tidak dapat menulis
45
karena literal5
, jadi kita harus menggandakannya dan membandingkan dengan 90 sebagai gantinya.sumber
u
adalah gabungan, jadi itu hanya masalah mengubah skor daripada sesuatu yang membatalkannya.)Mathematica,
625855 byteTiga byte terakhir yang disimpan sepenuhnya karena Martin Ender!
Fungsi tanpa nama mengambil argumen integer positif dan mengembalikan
True
atauFalse
.Algoritma rekursif, dengan
#4<4
menjadi basis kasus kebenaran (kita hanya perlu mengembalikanTrue
pada imput 1, tetapi kasus basis tambahan baik-baik saja). Jika tidak, kami menghitung pembagi terkecil-terkecil (yang seharusnya prima) dari input denganDivisors[#][[6-4]]
; jika lebih besar dari 2024 (44*46
) maka kita keluar denganFalse
, kalau tidak kita memanggil fungsi secara rekursif (menggunakan#6
set ke#0
) pada input dibagi dengan faktor prima kecil ini#
(yang harus kita ungkapkan sebagai#^-1
kali input#4
, karena/
tidak diizinkan).Secara struktural, babak pertama
#4<4||#<44*46&[#^-1#4]&
adalah fungsi anonim enam argumen, yang disebut dengan argumenDivisors[#][[6-4]]
,Null
,Null
,#
,Null
, dan#0
; ini adalah untuk mendapatkan sekitar larangan pada karakter2
,3
dan5
.Versi sebelumnya, yang menyelamatkan empat byte dengan mengganti
8018-6000
dengan44*46
, terinspirasi oleh ais523 Jelly jawaban (Martin Ender juga tampaknya terinspirasi oleh komentar ais523):Ini sangat buruk: Saya masih tidak tahu cara untuk benar-benar menetapkan variabel di Mathematica di bawah batasan ini! Baik
=
dane
diSet
dilarang. Menghindari+
dan)
juga merupakan masalah, tetapi tidak terlalu sulit untuk dikerjakan dengan mengorbankan lebih banyak byte.sumber
#2
juga akan dianulir, jadi Anda harus berhati-hati dengan bagaimana lambda Anda bersarang, dan kurangnya tanda kurung mungkin menyulitkan.)#4<4||#<44*46&[#^-1#4]&[Divisors[#][[6-4]],,,#,,#0]&
melempar banyak peringatan karena sekarang mencobaDivisors[#][[2]]
sebelum memastikan bahwa input lebih besar dari 1 (atau 3), tetapi hasilnya masih benar.Haskell,
4847 bytePada dasarnya terjemahan dari jawaban Dennis 'Jelly . xnatau menyimpan byte.
Digunakan
[…]!!0
sebagai tanda kurung karena)
dilarang, dansnd
+divMod
karenam
dimod
danrem
dilarang.sumber
!!0<1
dengan<[1]
. Tapi kelihatannya itu itu korsleting untuk digunakandiv
sebagai[\p n->p^n`div`n*n>p^n-1]!!0$product[1..44*46]
.\n->[0|p<-[product[1..44*46]^n],0<-[p,p-n..0]]
, yang menggunakan bahwa output hanya perlu konsisten.Pyke,
10879 byteCoba di sini!
Disimpan 1 byte dengan menggunakan cara Dennis menghasilkan 2025
sumber
Brachylog ,
910 byteCobalah online!
Pada dasarnya menggunakan algoritma yang sama dengan jawaban saya yang lain.
$ph
menemukanh
faktor prima pertama ($p
); ini adalah faktor prima terbesar, karena daftar faktor prima Brachylog berubah dari terbesar ke terkecil. Lalu saya mengambil akar kuadrat ($r
), ganda (*
), dan menguji untuk melihat apakah itu kurang dari 90 (<90
).Saya harus menggandakan input pertama karena 1 tidak memiliki faktor prima (dan dengan demikian tidak ada faktor prima pertama). Ini menambahkan faktor prima ekstra 2, yang tidak dapat memengaruhi apakah suatu angka gembur 2017, tetapi mencegah kegagalan saat menangani 1.
sumber
Sebenarnya , 9 byte
Terima kasih kepada Dennis untuk banyak byte!
Cobalah online!
Penjelasan:
sumber
Mathematica,
6674 byteTerima kasih kepada Dennis untuk menunjukkan bahwa
U+F4A1
ini dilarang.Penjelasan:
Divisors@#
: Daftar pembagi bilangan bulat dari argumen pertama#
.0<1
: Golf forTrue
(juga menghindari penggunaan surate
).Divisors@d^0
: Daftar formulir{1, 1, ..., 1}
dengan panjang sama dengan jumlah pembagid
.Tr
: Untuk daftar datar,Tr
kembalikan jumlah daftar itu. Dengan demikianTr[Divisors@d^0]
mengembalikan jumlah pembagid
.Function[{x,d},And[x,Tr[Divisors@d^0]>6-4||d<44*46]]
: Fungsi anonim dengan dua argumenx
dand
. Idenya adalah yangd
merupakan pembagi#
dan kami menguji untuk melihat apakah itu komposit atau kurang dari atau sama dengan2017
(inklusif).2017
-Friability setara dengan semua pembagi yang memenuhi kondisi ini. Sebagai ais523 ditemukan, menjadi prima kurang dari atau sama dengan2017
setara dengan menjadi prima kurang dari2025
. Seperti yang ditunjukkan Greg Martin , cukup untuk menguji apakah itu kurang dari2024=44*46
. Argumenx
bertindak sebagai akumulator untuk apakah semua pembagi yang dijumpai sejauh ini memenuhi properti ini. Kami kemudian meninggalkanFold
fungsi ini melalui semua pembagi#
dengan nilai awalTrue
, Karena kita memiliki akses ke tidakMap
atau/@
.sumber
05AB1E , 10 byte
Mengembalikan 1 jika benar, 0 sebaliknya.
Cobalah online!
Penjelasan
sumber
MATL , 15 byte
Output
0
untuk non-2017-friable atau1
untuk 2017-friable.Cobalah online! Atau verifikasi semua kasus uji .
Program ini memeriksa bahwa semua byte adalah komposit.
Penjelasan
sumber
Bash, 144 byte
Pengkodean ASCII:
Seperti biasa untuk shell, kode keluar menunjukkan berhasil (0) atau gagal (non-0).
Ini secara efektif merupakan pengejaan yang berbeda
Kami mendapatkan faktor terbesar dengan
factor $1|grep -o '[0-9]*$'
; yangtr -d :
adalah untuk khusus-kasus untuk = input1
.Ekspresi
$[6*6*69-466]
dievaluasi hingga 2018.Itu sulit digunakan
tr
untuk nama-nama perintah dan masih menggunakan substitusi perintah - saya tidak bisa menggunakan formulir bersarang$( )
, jadi saya akhirnya menyalurkan ke Bash lain untuk mengevaluasi hasilnya.Hasil tes:
Konfirmasi kode karakter:
sumber
Pyth, 11 byte
Cobalah online. Suite uji.
Gunakan trik Dennis untuk mendapatkan 2025, lalu periksa apakah tidak ada faktor input utama yang lebih besar.
sumber
Julia 0.4 ,
843837 byteHarapkan BigInt sebagai argumen.
Cobalah online! atau verifikasi bahwa tidak ada byte yang utama .
sumber
Japt , 14 byte
Mengembalikan 1 jika benar, 0 jika salah.
Coba di sini .
sumber
k
memiliki nilai primaBraingolf , 11 byte [sangat tidak bersaing]
Cobalah online!
Tidak dapat dibaca karena
ߢ
sekrup dengan angka, namun masih berfungsi dalam juru bahasa.Saya bahkan tidak memperhatikan batasan karakter ketika saya menulis ini, tetapi yang harus saya lakukan adalah mengubah karakter unicode yang aneh dari 2017 hingga 2018.
Mengingat 2018 bukan prima, setiap prima
<= 2018
juga<= 2017
Penjelasan
sumber