Definisi
Semiprime bebas persegi adalah bilangan alami yang merupakan produk dari dua bilangan prima yang berbeda.
Tugas
Dengan diberi nomor alami n
, hitung semua semiprim bebas persegi kurang dari atau sama dengan n
.
Detail
Harap tulis fungsi atau prosedur yang menerima parameter integer tunggal dan menghitung semua semi-square bebas kurang dari atau sama dengan parameternya. Hitungannya harus berupa nilai balik dari panggilan fungsi atau dicetak ke STDOUT.
Mencetak gol
Jawaban dengan jumlah karakter paling sedikit menang.
Jika terjadi seri, kriteria berikut akan digunakan secara berurutan:
Orang tertinggiKompleksitas waktu terbaik
- Kompleksitas ruang terburuk
Contohnya
f(1) = 0
f(62) = 18
f(420) = 124
f(10000) = 2600
console.log
?Jawaban:
J,
50403837 karakterPemakaian:
Dengan terima kasih kepada FUZxxl .
Uji kinerja
Saya bukan ahli teori seperti yang terlihat di sini di masa lalu, tapi saya pikir kompleksitas waktu adalah sesuatu seperti O (n p 2 ) di mana np adalah jumlah bilangan prima hingga dan termasuk nomor input n. Ini didasarkan pada asumsi bahwa kompleksitas metode saya (menghasilkan tabel perkalian yang sangat besar) jauh melebihi kompleksitas fungsi pembangkit utama yang dibangun pada J.
Penjelasan
f=:3 :'...'
mendeklarasikan kata kerja (monadik). Input ke kata kerja diwakili olehy
dalam definisi kata kerja.p:i._1&p:y
Katap:
kerjanya adalah kata kerja multi-tujuan bilangan prima, dan digunakan dalam dua cara berbeda di sini:_1&p:y
mengembalikan jumlah bilangan prima kurang dariy
itup:i.
menghasilkan setiap dari mereka. Menggunakan 10 sebagai input:(~:/**/)~
menghasilkan tabel yang saya bicarakan sebelumnya.*/
menghasilkan tabel perkalian,~:/
menghasilkan tabel tidak sama (untuk menghilangkan kotak) dan keduanya dikalikan bersama. Menggunakan output kami sebelumnya sebagai input:}.~.,
sekarang kita mengubah angka menjadi satu daftar,,
dapatkan nilai unik~.
dan hapus 0 di awal}.
y<:
perbandingan dengan input asli untuk memeriksa nilai mana yang valid:+/
dan kemudian jumlahkan itu untuk mendapatkan jawabannya.sumber
+/-.x<}.~.,(~:/~*[*/])p:i._1&p:[x=.n
mana n adalah input.f=:3 :'+/-.y<}.~.,(~:/~*[*/])p:i._1&p:y'
untuk 40 karakter?3 :'...'
Mathematica
656455514739Kode
Yang berikut menghitung jumlah semiprim bebas persegi kurang dari atau sama dengan
n
:Setiap faktor semiprime bebas persegi ke dalam struktur formulir:
{{p,1}{q,1}}
Misalnya,Rutin hanya menghitung angka dalam rentang yang diinginkan yang memiliki struktur faktor ini.
Pemakaian
Waktu: Semua contoh yang diberikan
Waktu: n = 10 ^ 6
Dibutuhkan di bawah empat detik untuk menghitung jumlah semi-primes bebas persegi kurang dari atau sama dengan satu juta.
sumber
=
dan setelah,
benar - benar diperlukan secara sintaksis?Python, 115
sumber
f=lambda x:sum([(i*j<=x)&p(j)&p(i)for i in r(2,x)for j in r(2,i)])
menghemat 5 karakter.itertools
di kepalaku.Jelly , 7 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Python (139)
Harap berikan beberapa hasil sampel sehingga pesaing dapat menguji program mereka.
sumber
Ruby 82
Demo: http://ideone.com/cnm1Z
sumber
Python 139
sumber
Golfscript 64
Demo online di sini
Catatan: Dalam demo di atas saya mengecualikan
420
dan10000
menguji kasus. Karena uji primality yang sangat tidak efisien, program tidak dapat mengeksekusi untuk input ini dalam waktu kurang dari 5 detik.sumber
Shell, 40
Pemakaian:
sumber
Jelly ,
1413 byteCobalah online!
Kritik konstruktif disambut!
sumber
⁼
danS
dapat diubah menjadi penggunaanċ
(Hitung). Anda dapat menggunakan hingga 10 byte. Saya akan membiarkan Anda menyelesaikannya!Python 2/3 ,
9594 byteCobalah online!
Diposting dalam tantangan berusia 6 tahun karena membuat rekor Python baru, IMO itu pendekatan yang cukup menarik.
Penjelasan
Python 2/3 (PyPy) ,
888281 byteCobalah online!
Didasarkan pada golf 92-byte oleh Value Ink. PyPy diperlukan untuk menafsirkan dengan benar
0or
, karena standar Python melihat ini sebagai upaya angka oktal.sumber
Stax , 8 byte
Jalankan dan debug itu
Dibongkar, tidak diserang, dan dikomentari, sepertinya ini.
Jalankan yang ini
sumber
Perl 6 ,
5845 byteTerima kasih kepada Jo King untuk -13 byte.
Mengambil keuntungan dari fakta bahwa bilangan bulat dengan empat faktor adalah semiprim bebas persegi atau kubus sempurna.
Cobalah online!
sumber
Brachylog , 7 byte
Cobalah online!
sumber
Retina , 58 byte
Cobalah online!
Dibawa sebagai input unary dengan
_
tanda penghitunganPenjelasan
Angka adalah semi-prime bebas persegi jika faktor terbesar dan terkecil, tidak termasuk dirinya sendiri dan 1, keduanya merupakan bilangan prima.
Mengambil input dan menghasilkan setiap nomor unary kurang dari atau sama dengan itu, masing-masing pada jalurnya sendiri
Kemudian, untuk setiap nomor ...
Temukan faktor terkecil dan terbesarnya, tidak termasuk 1 ...
dan hitung jumlah mereka yang prima. Karena faktor terkecil harus prima, ini mengembalikan 1 atau 2
Hitung jumlah total 2-an
sumber
Python 2 ,
105104 byteCobalah online!
1 byte thx ke squid 🦑
sumber
(p*p)
bisap**2
Ruby
-rprime
, 64 byteSaya tahu bahwa ada solusi Ruby lain di sini, tapi saya tidak ingin menabraknya dengan komentar sejak dijawab pada tahun 2012 ... dan ternyata, menggunakan bendera program menghitungnya sebagai bahasa yang berbeda , jadi saya rasa ini secara teknis bukan "Ruby".
Cobalah online!
Penjelasan
sumber
APL (NARS), karakter 26, byte 52
uji:
ini adalah alternatif yang lebih panjang (59 karakter yang saya inginkan)
uji:
sumber