Masalah
Tujuannya adalah seperti judulnya mengatakan untuk menemukan prime ke-n sehingga prime - 1 dapat dibagi oleh n.
Penjelasan
Berikut ini adalah contoh sehingga Anda memahami pertanyaannya, ini belum tentu cara itu harus diselesaikan. Itu hanya sebagai cara untuk menjelaskan pertanyaan itu
diberikan 3 sebagai input pertama kita akan melihat semua bilangan prima
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 ...
Kemudian kita memilih bilangan prima sehingga bilangan prima - 1 dapat dibagi oleh n (3 dalam hal ini)
7 13 19 31 37 43 61 67 73 79 97 103 107 109 127 ...
Kami kemudian memilih istilah ke-n dalam urutan ini
Kami akan menghasilkan 19 untuk input 3
Catatan
Kita juga dapat menganggap ini sebagai prima ke-n dalam urutan {1, n + 1, 2n + 1, 3n + 1 ... kn + 1} di mana k adalah bilangan asli
Uji Kasus
1 --> 2
2 --> 5
3 --> 19
4 --> 29
100 --> 39301
123 --> 102337
code-golf
number
number-theory
primes
Ando Bando
sumber
sumber
Jawaban:
05AB1E ,
98 byte05AB1E menggunakan pengkodean CP-1252 .
Menyimpan satu byte berkat Osable
Cobalah online!
Penjelasan
sumber
µN¹*>Dp½
yang menyimpan satu byte dan mempercepat perhitungan.Python 2, 58 byte
sumber
Mathematica, 48 byte
Fungsi tanpa nama mengambil argumen tunggal, yang diberi nama
n
. Buat daftarn^3
bilangan prima pertama , pilih yang kongruen dengan 1 modulon
, lalu ambiln
elemen ke-5 hasilnya. Ini berjalan dalam beberapa detik pada input 123.Saat ini tidak diketahui apakah selalu ada prime prime, di antara
n^3
bilangan prima pertama , yang kongruen dengan 1 modulon
, apalagin
di antaranya. Namun, algoritma dapat dibuktikan benar (setidaknya untuk besarn
) dengan asumsi hipotesis Riemann yang digeneralisasi !sumber
Haskell,
5947 byteContoh penggunaan:
f 4
->29
.Bagaimana itu bekerja:
Sunting: Terima kasih @Damien untuk 12 byte dengan menghapus tes keterbagian dan hanya melihat kelipatan di tempat pertama.
sumber
f n=[p|p<-[1,n+1..],all((<2).gcd p)[2..p-1]]!!n
Jelly , 9 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Java 7, 106 byte
Tidak Disatukan:
Kode uji:
Cobalah di sini (hasil uji terakhir menghasilkan batas waktu terlampaui pada ideone)
Keluaran:
sumber
System.out.println
besar ditambahkan sehingga Anda melihat input apa yang telah saya gunakan untuk memberikan output yang ditampilkan, dan semuanya juga diberikan jika ada yang ingin menyalin-menempelkannya di IDE mereka untuk bermain-main.Nasm 679 byte (Instruksi Intel 386 cpu 120 byte)
ini adalah ungolfed dan hasilnya
sumber
Sebenarnya , 13 byte
Selamat datang saran bermain golf! Cobalah online!
Tidak melakukanolf
sumber
Common Lisp, 162 byte
Pemakaian:
Tidak Disatukan:
Beberapa
loop
konstruksi itu mungkin dapat disingkat menjadido
loop, tetapi inilah yang saya miliki untuk saat ini.sumber
MATL , 12 byte
Cobalah online!
(Untuk memasukkannya
123
habis dalam kompiler online, tetapi berfungsi secara offline.)Penjelasan
sumber
Perl,
7776 + 1 = 77 byteMenggunakan regex pengujian utama untuk menentukan apakah
$p
prime, dan memastikan bahwa itu kongruen dengan 1 mod input (satu-satunya bilangan bulat negatif di bawah 2 adalah 0 dan 1, tetapi itu tidak bisa 0 jika itu prima, sehingga harus menjadi 1. menghemat 1 byte lebih dari==1
).sumber
(1 x++$.)!~/^(11+?)\1+$/&&($.%$_<2)&&push@a,$.while@a<$_;say$a[-1]
(itu yang saya bicarakan di komentar saya sebelumnya). Namun output (dari kedua versi) tampaknya salah untuk setidaknya 2 dan 3 ...Mathematica 44 Bytes
Sangat cepat. Menggunakan ide dari "Catatan"
Keluaran
sumber
Perl 6 ,
46 3937 bytesumber
Java 8, 84 byte
Golf
Tidak disatukan
Penjelasan
Solusi yang terinspirasi oleh beberapa jawaban lain. Fungsi adalah lambda yang mengharapkan satu int.
Itu
n>1?i:2
adalah hack murah karena saya tidak tahu cara yang lebih baik untuk mempertimbangkan kasus n = 1.Juga, solusi ini kadaluwarsa pada Ideone, tetapi telah diuji untuk semua kasus uji. Itu habis karena untuk mencukur beberapa byte, saya mengeluarkan
j<i
cek eksplisit di loop dalam. Sebagian besar tersirat olehi%j>0
... kecuali dalam kasusi=1
danj=2
(iterasi pertama), dalam hal ini loop berjalan sampai j meluap (saya berasumsi). Kemudian itu berfungsi dengan baik untuk semua iterasi sesudahnya.Untuk versi yang tidak time out beberapa pasangan lebih lama, lihat di sini!
sumber
Racket 109 byte
Tidak Disatukan:
Pengujian:
Keluaran:
sumber
Ruby 64 byte
Disebut seperti ini:
Juga, aplikasi baris perintah ini berfungsi:
disebut seperti ini
tapi saya tidak begitu yakin bagaimana cara menghitung karakter. Saya pikir saya dapat mengabaikan nama bahasa, tetapi harus menyertakan
-rprime
dan spasi sebelum nama skrip, sehingga sedikit lebih pendek, yaitu 63. . .sumber
R, 72 byte
Sangat tidak efisien dan lambat tetapi berhasil. Bunyinya input dari stdin dan kemudian menggunakan
isPrime
fungsi darinumbers
paket untuk menemukan bilangan prima. Sisanya hanya memeriksa apakahprime - 1
habis dibagin
.sumber
JavaScript (ES6), 65 byte
Menggunakan penguji primitif regexp, karena a) 8 byte lebih pendek dan b) kurang rekursif daripada pendekatan rekursif murni saya.
sumber
Aksioma 64 byte
apakah seseorang tahu cara menulis di atas menggunakan streaming Aksioma? ... beberapa contoh
Jenis: Tuple NonNegativeInteger
sumber