Sebuah kekuatan utama adalah bilangan bulat positif n yang dapat ditulis dalam bentuk n = p k mana p adalah prima dan k adalah bilangan bulat positif. Sebagai contoh, beberapa kekuatan utama adalah [2, 3, 5, 4, 9, 25, 8, 27, 125]
.
Selanjutnya, pertimbangkan kekuatan utama 2. Ini adalah [2, 4, 8, 16, ...]
dan dapat ditulis dalam bentuk 2 k . Mereka semua akan dimasukkan ketika mempertimbangkan kekuatan utama di bawah 20. Namun, 16 adalah kekuatan prima maksimal dengan basis prima 2 dalam rentang itu. Kekuatan prima p k adalah maksimal dalam suatu rentang jika itu adalah kekuatan tertinggi dari p dalam rentang itu. Kami hanya tertarik pada kekuatan prima maksimal di setiap rentang sehingga semua kekuatan prima yang lebih rendah harus dikecualikan.
Tujuan Anda adalah untuk menulis fungsi atau program yang mengambil bilangan bulat positif n dan output maksimal kekuatan utama dalam kisaran [2, 3, 4, ..., n]
.
Terima kasih kepada @ Peter Taylor untuk mengklarifikasi definisi kekuatan prima maksimal dan banyak lagi.
Aturan
- Ini adalah kode-golf jadi buat kode Anda sesingkat mungkin.
- Kekuatan prima maksimal dapat berupa output dalam urutan apa pun tetapi tidak boleh ada duplikat.
Uji kasus
n result
1 []
2 [2]
3 [2, 3]
4 [3, 4]
5 [3, 4, 5]
6 [3, 4, 5]
7 [3, 4, 5, 7]
20 [5, 7, 9, 11, 13, 16, 17, 19]
50 [11, 13, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49]
100 [11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97]
10000 <1229 results>
[101, 103, 107, 109, 113, 127, 131, 137, 139, 149, ..., 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]
Daftar lengkap kekuatan prima maksimal untuk 10.000 dapat ditemukan di sini .
Power floor
Apa-apaanMathematica,
444340 byteDisimpan 4 byte berkat miles dan Martin Ender
n#^⌊#~Log~n⌋&/@Select[Range@n,PrimeQ]
⌊
dan⌋
adalah3
karakter byteU+230A
danU+230B
mewakili\[LeftFloor]
dan\[RightFloor]
masing-masing.Penjelasan:
Fungsi murni.
#
kependekanSlot[1]
yang merupakan argumen pertama keFunction
.PrimePi@#
menghitung jumlah bilangan prima yang kurang atau sama dengan#
,Range@PrimePi@#
adalah daftarPrimePi[#]
bilangan bulat positif pertama , dan demikianPrime@Range@PrimePi@#
juga daftar bilangan prima lebih kecil atau sama dengan#
(ini satu byte lebih pendek dariSelect[Range@#,PrimeQ]
). Simbolx
adalahSet
sama dengan daftar ini, kemudian diangkat kePower
⌊x~Log~#⌋
, yang merupakan daftarFloor[Log[n,#]]
untuk setiapn
dix
. Dalam Mathematica, menaikkan daftar ke daftarPower
lain dengan panjang yang sama menghasilkan daftar kekuatan elemen yang sesuai.sumber
Range@#~Select~PrimeQ
akan lebih pendek dariPrime@Range@PrimePi@#
... tapi ini dasiTreeForm
MATL, 13 byte
Cobalah secara Online!
Penjelasan
sumber
Jelly , 8 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Jelly ,
129 byteCobalah online! (Metode terlalu lambat untuk kasus 10000).
Bagaimana?
Membangun daftar p k di urutan p .
sumber
Pyth, 13 byte
Coba di sini!
Saya belum pernah bermain dengan Pyth sehingga tip golf apa pun dihargai.
sumber
Saya tidak bisa mendapatkan solusi Mathematica yang lebih pendek daripada solusi ngenisis , tetapi saya pikir saya akan menawarkan beberapa pendekatan alternatif (semoga menarik).
Mathematica, 65 byte
Pertama-tama kita gunakan
{#,#}&/@Range@#~Select~PrimeQ
untuk membuat daftar semua bilangan prima dalam kisaran yang sesuai, tetapi dengan pasangan terurut dari setiap prime, seperti{ {2,2}, {3,3}, ...}
. Kemudian kami beroperasi pada daftar itu berulang kali dengan aturan penggantian{a_,b_}/;a<=#:>{b a,b}
, yang mengalikan elemen pertama dari pasangan yang dipesan dengan yang kedua hingga elemen pertama melebihi input. Kemudian kita berlaku#/#2&@@@
untuk output, untuk setiap pasangan yang dipesan, elemen pertama dibagi dengan yang kedua. (Mereka akhirnya disortir oleh prime yang mendasarinya: contoh outputnya adalah{16, 9, 5, 7, 11, 13, 17, 19}
.)Mathematica, 44 byte
Fungsi von Mangoldt
Λ(n)
adalah fungsi jumlah teori yang menarik: itu sama dengan 0 kecualin
adalah seorang perdana listrik p k , dalam hal ini sama denganlog p
(tidaklog n
). (Ini adalah log natural, tetapi itu tidak masalah.) Dengan demikianMangoldtLambda@#->#&~Array~#
membuat array aturan{ 0->1, Log[2]->2, Log[3]->3, Log[2]->4, Log[5]->5, 0->6, ... }
yang panjangnya adalah bilangan bulat input.Kami kemudian mengubah daftar aturan ini menjadi "asosiasi" menggunakan
<|...|>
. Ini memiliki efek mempertahankan hanya aturan terakhir dengan nilai tangan kiri yang diberikan. Dengan kata lain, itu akan membuangLog[2]->2
danLog[2]->4
danLog[2]->8
dan hanya menyimpanLog[2]->16
(dengan asumsi bahwa input antara 16 dan 31 untuk contoh ini). Oleh karena itu satu-satunya sisi kanan yang tersisa adalah kekuatan prima maksimal — kecuali untuk aturan yang tersisa0->n
, di manan
daya non-prima terbesar hingga bilangan bulat input. TetapiRest
membuang aturan yang tidak diinginkan, danValues
ekstrak sisi kanan dari aturan dalam asosiasi. (Mereka akhirnya disortir seperti di atas.)Versi yang sedikit lebih panjang (46 byte), yang menghitung jumlah penampilan masing-masing
log p
dan kemudian secara eksponensial dikonversi menjadi kekuatan prima maksimal:sumber
CJam ,
2120 byteDisimpan 1 byte berkat Martin Ender
Cobalah online!
Penjelasan
sumber
Brachylog , 15 byte
Cobalah online!
Ini menghasilkan kekuatan dari yang terbesar hingga yang terkecil.
Ini sangat tidak efisien.
Penjelasan
Ini akan menemukan dekomposisi prime terbesar untuk setiap prime terlebih dahulu karena cara
⊇
kerjanya: dari kiri ke kanan dan dari himpunan bagian terbesar ke terkecil.sumber
Brachylog ,
242119 byte3 + 2 byte disimpan berkat Fatalize!
Ini adalah pertama kalinya saya menggunakan Brachylog, dan saya tahu beberapa hal bisa dilakukan dengan cara yang lebih pendek, tapi saya senang itu berhasil: D
Cobalah online! (Nilai pengembalian dipesan oleh bilangan prima basis mereka)
Penjelasan:
sumber
?
dan.
untuk Input dan Output, alih-alihI
danX
, dengan demikian:{≥N~^.hṗ:N×>?∧0<~t}ᶠ^ᵐ
0<~t
dan menyatakan bahwa setiap elemen dari Output.
adalahℕ₁ = [1, ..., +inf)
seperti:{≥N~^.ℕ₁ᵐhṗ:N×>?∧}ᶠ^ᵐ
{≥.~^ℕ₁ᵐhṗ:.×>?∧}ᶠ
(menggunakan N langsung sebagai output) tidak berfungsi? Saya mencoba dulu sesuatu seperti ini, tetapi kemudian harus menggunakan X dan menerapkannya{...}ᶠ
yang menyebabkan perilaku aneh. Saya bermaksud mengubahnya dan saya akan melihat secara spesifik mengapa program ini tidak bekerja dengan cara yang sama seperti di atas.{≥.~^ℕ₁ᵐhṗ:.≜×>?∧}ᶠ
Dengan begitu Anda mendapatkan labelisasi yang benar. (Perubahan dibuat untuk spesifikasi sementara itu tetapi tidak benar-benar mengubah perilaku program khusus ini, sehingga tidak membuatnya tidak bersaing). Ini menghemat 2 byte05AB1E ,
1512 byteCobalah online!
Penjelasan
sumber
Utilitas Bash + GNU, 74 byte
Cobalah online!
Nomor input dilewatkan sebagai argumen. Outputnya dicetak ke stdout. (Seperti biasa, stderr diabaikan.)
Output sampel:
Begini cara kerjanya:
Sebut argumen N.
seq
menghasilkan semua angka dari 1 hingga N, danfactor
faktor semuanya.Regex dalam panggilan ke sed mengidentifikasi garis-garis di mana nomor tersebut adalah P prima, dan menggantikan garis-garis itu dengan garis-garis yang berbentuk `
(di mana P dan N diganti dengan nilai numerik aktualnya, dan semua yang lain disalin secara harfiah, bahkan tanda kutip dan titik koma, dan string
print
).Baris-baris ini dimasukkan sebagai input ke
bc -l
; bc mencetak nilai dari tiga angka yang ditunjukkan, masing-masing diikuti oleh baris baru, dan kemudian mencetak karakter/^p
. (Dalam bc, l (x) menunjukkan logaritma natural x.) JK KString yang dicetak bc kemudian diumpankan sebagai input ke dc; dc mencetak nilai setiap P ^ (log (N) / log (P)) menggunakan bilangan bulat aritmatika (memotong); itulah kekuatan terbesar dari P yaitu <= N.
Satu hal yang dipoles di atas adalah apa yang terjadi pada garis yang dihasilkan oleh faktor-faktor yang tidak sesuai dengan bilangan prima. Garis-garis itu tidak cocok dengan regex dalam panggilan ke sed, jadi tidak ada penggantian dilakukan pada mereka. Akibatnya, garis-garis itu mulai dengan angka yang diikuti oleh titik dua, yang menghasilkan kesalahan ketika dimasukkan sebagai input
bc
. Tapi bc hanya mencetak ke stderr lalu, yang kita abaikan; itu tidak mencetak apa pun untuk stdout. Secara default, stderr diabaikan di PPCG .sumber
Haskell ,
73 6766 byteCobalah online! Pemakaian:
Sunting: lepas 6 byte berkat Zgarb!
Penjelasan:
sumber
last[x^i|i<-[1..n],x^i<=n]
.Jelly , 9 byte
Satu byte lebih lama dari jawaban saya yang lain , tetapi selesai untuk input 10.000 adalah beberapa detik.
Cobalah online!
Bagaimana itu bekerja
sumber
JavaScript (ES6),
118120119114112105 byteSaran diterima. Ini agak lama, tetapi sepertinya layak diposkan karena melakukan semua pengujian keterbagian secara eksplisit daripada menggunakan bawaan yang terkait dengan bilangan prima.
Catatan:
sumber
Sage, 43 byte
Peta setiap prime dalam kisaran
primes(i)
ke kekuatan prima maksimal.ln
hanya aliaslog
sehingga menerima basis alternatif meskipun namanya hanya bisa menggunakan basise
.sumber
primes
fungsinya dan menjadi sangat bersemangat. Jangan pernah mempercayai stackoverflow lagi.Haskell,
11090 byte--duperbarui per umpan balik Laikoni
sumber
Exception: Prelude.last: empty list
untukf 2
danf 3
.f 4
mengembalikan[2,3]
bukannya[4,3]
, saya pikir AndatakeWhile(<n)
kebutuhan untuk menjaditakeWhile(<=n)
. Namun menggunakanfst.span
bukannyatakeWhile
satu byte lebih pendek.Haskell , 70 byte
Menentukan fungsi
f
. Cobalah online!Penjelasan
Idenya adalah untuk menyaring rentang
[2..n]
untuk angka-angkak
yang memuaskank == p^length(divisors k)
danp*k > n
, di manap
adalah pembagi utama terkecilk
.sumber
PHP,
101939188 bytehanya sedikit matematika sungguhan ...
kerusakan
sumber
JavaScript ES7, 93 byte
Ulangi secara berulang
i
dari 0 hingga dan termasukn
. Jikai
prima naikkan ke eksponen berlantai tertinggi yang membuatnya<= n
(i ^ floor(log(n) / log(i))
)sumber