pengantar
The Prime Menghitung Function , juga dikenal sebagai Pi fungsi , mengembalikan jumlah bilangan prima kurang dari atau sama dengan x.
Tantangan
Program Anda akan mengambil bilangan x yang Anda anggap positif, dan menghasilkan bilangan bulat tunggal yang sama dengan jumlah bilangan prima kurang dari atau sama dengan x. Ini adalah tantangan kode-golf , jadi pemenangnya adalah program dengan byte paling sedikit.
Anda dapat menggunakan bahasa apa pun yang Anda pilih asalkan sudah ada sebelum tantangan ini naik, tetapi jika bahasa tersebut memiliki fungsi penghitungan prime bawaan atau fungsi pemeriksaan primality (seperti Mathematica), fungsi itu tidak dapat digunakan dalam kode Anda .
Contoh Input
Input:
1
Keluaran:
0
Input:
2
Keluaran:
1
Input:
5
Keluaran:
3
Jawaban:
05AB1E , 3 byte
Ini mengasumsikan bahwa built-in faktorisasi diperbolehkan. Cobalah online!
Bagaimana itu bekerja
sumber
Python 2, 45 byte
Menggunakan generator utama Teorema Wilson . Produk
p
melacak(k-1)!^2
, danp%k
adalah 1 untuk bilangan prima dan 0 untuk nonprima.sumber
MATL ,
11, 10, 8, 5 byteCobalah online!
Saya menulis versi yang memiliki penjelasan yang sangat keren tentang cara kerja matriks MATL:
:YF!s1=1
Tapi itu tidak lagi relevan. Periksa riwayat revisi jika Anda ingin melihatnya.
Penjelasan baru:
Tiga byte disimpan berkat solusi jenius Dennis
sumber
YF!s1=s
Jelly ,
85 byte3 byte disimpan berkat @Dennis!
Cobalah online!
Port jawaban MATM DJMcMayhem (versi sebelumnya) disempurnakan oleh Dennis.
sumber
ÆE
, karena setiap eksponen sesuai dengan faktor prima yang berbeda.RÆESL
hanya mencapai itu.!ÆEL
akan lebih pendek.Templat MediaWiki dengan ParserFunctions , 220 + 19 = 239 byte
Untuk memanggil templat:
Diatur dalam gaya Lisp:
Hanya tes primality dasar dari 2 hingga n . Angka-angka dengan tiga kawat gigi di sekitar mereka adalah variabel, di mana
{{{1}}}
adalah n ,{{{2}}}
adalah jumlah yang diuji,{{{3}}}
adalah faktor untuk memeriksa.sumber
Perl, 33 byte
Termasuk +1 untuk
-p
Berikan nomor input pada STDIN
primecount.pl
Memberikan hasil yang salah untuk
0
tetapi tidak apa-apa, op meminta dukungan untuk bilangan bulat positif saja.sumber
Retina, 31 byte
Hitungan byte mengasumsikan penyandian ISO 8859-1. Konversikan input ke unary, buat rentang dari
1
ken
, masing-masing pada jalurnya sendiri. Cocokkan bilangan prima.Cobalah online - Masukkan jauh lebih besar dari 2800 kali atau kehabisan memori.
Referensi:
Generator jarak Martin
Pemeriksa utama Martin
sumber
Jelly , 3 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Jelly ,
13 11 10 9 8 76 byteTidak menggunakan fungsi prime
bawaan apa pun -1 byte berkat @miles (gunakan tabel)
-1 byte terima kasih ke @Dennis (konversi dari unary untuk menghitung pembagi)
TryItOnline
Atau lihat 100 syarat pertama dari seri ini
n=[1,100]
, juga di TryItOnlineBagaimana?
sumber
%þ`¬Sċ2
menggunakan tabel sisa.ḍþḅ1ċ2
menghemat satu byte.JavaScript (ES6),
4543 byteModifikasi fungsi primality
363533 byte saya (1 byte disimpan oleh @Neil, 2 oleh @Arnauld):(Saya tidak dapat memposting ini di mana pun karena Apakah nomor ini utama? Hanya menerima program lengkap ...)
Cuplikan tes
Tampilkan cuplikan kode
sumber
&
di tengah fungsi primality Anda.PowerShell v2 +, 98 byte
Perhatian: Ini lambat untuk input besar.
Pada dasarnya pencarian berdasarkan unary dari Apakah nomor ini prima? , ditambah dengan
for
loop dan$j++
penghitung. Sedikit logika tambahan di bagian depan untuk memperhitungkan input kasus tepi1
dan2
, karena cara kerja fenceposting difor
loop.sumber
05AB1E , 5 byte
Diasumsikan bahwa builtin faktorisasi utama diperbolehkan.
Kode:
Penjelasan:
Menggunakan pengkodean CP-1252 . Cobalah online!
sumber
ÅPg
apa yang akan terjadi sekarang, kan?CJam , 7 byte
Cobalah online! Menggunakan fungsi faktorisasi.
Penjelasan:
sumber
Jelly , 6 byte
Ini hanya menggunakan aritmatika dasar dan teorema Wilson. Cobalah online! atau verifikasi semua kasus uji .
Bagaimana itu bekerja
sumber
C # 5.0
7877Tidak disatukan
sumber
Pyth -
76 byteKarena yang lain menggunakan fungsi faktorisasi prima ...
Test Suite .
sumber
Bash + coreutils, 30
Ideone.
Paket Bash + coreutils + BSD-games, 22
Jawaban pendek ini mengharuskan Anda memiliki bsdgames paket yang diinstal:
sudo apt install bsdgames
.sumber
Pyke,
86 byteCoba di sini!
Terima kasih kepada Maltysen untuk algoritma baru
sumber
C #, 157 byte
Program lengkap dengan uji kasus:
Mulai mengambil beberapa saat setelah Anda pergi di atas 1 juta.
sumber
Matlab, 60 byte
Melanjutkan lampiran saya ke fungsi Matlab satu baris. Tanpa menggunakan faktorisasi bawaan:
Mengingat bahwa bilangan prima
y
hanya memiliki dua faktor[1,y]
: kita menghitung angka dalam rentang[1,x]
yang hanya memiliki dua faktor.Menggunakan factorisation memungkinkan untuk pemendekan yang signifikan (turun ke 46 byte).
Kesimpulan: Perlu melihat ke dalam mereka bahasa golf: D
sumber
Sebenarnya 10 byte
Ini adalah solusi terpendek yang saya temukan yang tidak mengalami bug juru bahasa di TIO. Saran bermain golf diterima. Cobalah online!
Tidak melakukanolf
sumber
Jelly , 3 byte
Jelly memiliki fungsi penghitungan prima built-in,
ÆC
dan fungsi pengecekan primaÆP
, ini menggunakan fungsi pembangkit prima built-in,ÆR
dan memakan waktu lamaL
.Saya kira ini adalah tentang batas menggunakan faktorisasi bawaan bawaan, yang juga akan memakan waktu 3 byte
!Æv
(!
faktorial,Æv
hitung faktor prima)sumber
PHP,
9692 byteDisimpan 4 byte berkat Roman Gräf
Tes online
Kode pengujian tidak digabungkan:
Tes online
sumber
isInt(...)?1:0
dan bukan hanyaisInt(...)
APL (Dyalog Unicode) , 13 byte SBCS
Cobalah online!
⍳
ɩ ndices 1…N⧽
∘.|
tabel sisa (menggunakan keduanya sebagai sumbu)⍳
ɩ ndices 1 ... N0+.=
jumlah elemen yang sama dengan nol (yaitu berapa banyak pembagi masing-masing memiliki)2+.=
jumlah elemen sama dengan dua (yaitu berapa banyak bilangan prima yang ada)sumber
Python 3, 40 byte
Bilangan bulat ganjil adalah bilangan prima jika hanya 2 ** (k-1) kongruen dengan 1 mod k. Jadi, kami hanya memeriksa kondisi ini dan menambahkan 1 untuk kasus k = 2.
sumber
MATL , 9 byte
Ini menghindari dekomposisi faktor prima. Kompleksitas adalah O ( n ²).
Cobalah online!
sumber
JavaScript (ES6),
50 + 246 + 243 byteDisimpan
35 byte berkat Neil:eval
dapat mengaksesn
parameter.The
eval(...)
memeriksa apakahn
perdana.Solusi sebelumnya:
Hitungan byte harus +2 karena saya lupa memberi nama fungsi
f=
(diperlukan untuk rekursi)46 + 2 byte (Disimpan 3 byte berkat produk ETH):
50 + 2 byte:
sumber
eval
dapat mengaksesn
parameter ke fungsi Anda (yang Anda lupa namanya, dikenakan biaya 2 byte; ada baiknya mengetahui bahwa saya bukan satu-satunya yang membuat kesalahan itu) yang menghemat 5 byte.eval
. Diuji dengan firefox, chrome dan edge, itu bekerja untuk saya. Penjelasannya adalah eval () diuraikan dalam konteks pernyataan . Dua contoh:a=12;f=b=>eval('a + 5');f(8)
menampilkan17
dana=12;f=a=>eval('a + 5');f(8)
menampilkan13
.Java 7.102 byte
Paksaan
Tidak disatukan
sumber
1
. Saat ini kembali1
bukan0
. Anda dapat memperbaiki hal ini dengan baik mengubahreturn c;
kereturn n<2?0:c;
atau mengubah,c=1,
ke,c=n<2?0:1,
.q 35 byte
sumber
Sebenarnya 10 byte
Jika jawaban Sebenarnya saya yang pertama tidak diizinkan untuk menggunakan fungsi penghasil prima, berikut adalah jawaban cadangan menggunakan teorema Wilson. Saran bermain golf diterima. Cobalah online!
Cobalah online
sumber