Sebuah kesenjangan utama adalah perbedaan antara dua bilangan prima berturut-turut. Lebih khusus lagi, jika p dan q adalah bilangan prima dengan p < q dan p +1, p +2, ..., q −1 bukan bilangan prima, bilangan prima p dan q mendefinisikan celah n = q - p . Kesenjangan dikatakan dimulai oleh p , dan memiliki panjang n .
Diketahui bahwa ada kesenjangan prima yang besar secara arbitrer. Artinya, mengingat n ada kesenjangan utama panjang n atau lebih besar. Namun, kesenjangan utama panjang persis n mungkin tidak ada (tetapi yang lebih besar akan).
Tantangan
Dengan bilangan bulat positif n
, hasilkan prime pertama yang memulai celah panjang n
atau lebih besar.
Sebagai contoh, untuk input 4
output harus 7
, karena 7 dan 11 adalah bilangan prima berturut-turut pertama yang berbeda setidaknya 4 (celah sebelumnya adalah 1, dari 2 hingga 3; 2, dari 3 ke 5; dan 2, dari 5 ke 7). Untuk input 3
, jawabannya juga harus 7
(tidak ada kesenjangan dengan panjang 3).
Aturan tambahan
Algoritme secara teoritis seharusnya bekerja untuk tinggi sembarang
n
. Dalam praktiknya, dapat diterima jika program dibatasi oleh waktu, memori, atau ukuran tipe data.Input dan output dapat diambil dengan cara apa pun yang wajar .
Program atau fungsi diizinkan, dalam bahasa pemrograman apa pun . Celah standar dilarang.
Kode terpendek dalam byte menang.
Uji kasus
Input -> Output
1 2
2 3
3 7
4 7
6 23
10 113
16 523
17 523
18 523
30 1327
50 19609
100 370261
200 20831323
sumber
Jawaban:
Gaia , 6 byte
Ini sangat tidak efisien (
16
test case membutuhkan lebih dari satu jam untuk menghitung pada mesin saya).Cobalah online!
Penjelasan
Urutannya tampaknya memiliki properti yang a (n) <= 2 ^ n .
sumber
Jelly ,
10, 9, 810 byteCobalah online!
Dua byte disimpan berkat @Dennis! (dan kemudian ditambahkan kembali karena kasus tepi)
Penjelasan:
sumber
#
akan dihitung dari input di sini) Tampaknya masuk akal untuk menganggap ini, tetapi saya tidak tahu apakah itu asumsi yang valid. EDIT: FYI untuk memperbaiki awalan (jika perlu) dengan2ð
Mathematica, 30 byte
Cobalah online!
Mathematica, 35 byte
Cobalah online!
Mathematica, 77 byte
sumber
p
danq
prima ... Kode pertama tampaknya tidak valid, karena hanya naik hingga 65535 kecuali Anda secara eksplisit memberi makan argumenMaxIterations
.(For[t=2,NextPrime@t-t<#,t++];t)&
Haskell ,
106 102 93 77 7372 byteIni menghasilkan daftar bilangan prima tak terbatas pertama, kemudian mencari celah utama. Daftar utama diambil dari sini . Mungkin bisa dipersingkat, tapi saya belum tahu caranya :)
Terima kasih kepada @BruceForte untuk -4 byte dan @Zgrab untuk -1 byte!
Cobalah online!
sumber
zip=<<tail$[...]
menghemat satu byte.n
itu akan berhenti setelah waktu yang terbatas :) (Haskell bukan prosedural, tetapi bahasa fungsional dengan evaluasi malas.)Pyth - 14 byte
Ini memfilter dari [1, inf), memfilter menurut primality (
P_
) dan bahwa prime berikutnya yang difilter dari (n, inf), memiliki> yang berbeda = ke input.Test Suite .
sumber
PowerShell ,
979691 byteCobalah online!
Mengambil input
$n
, set$a
dan$b
sama dengan2
, lalu memasukifor
loop tak terbatas . Di dalam, kita teruskan$b
sampai kita mencapai prime berikutnya . Kemudian kami memeriksa apakah$b-$a
(yaitu kesenjangan) adalah-g
kualifikasi ataue
untuk$n
. Jika ya, kami output$a
danexit
. Kalau tidak, kami menetapkan$a
untuk menjadi$b
dan meningkat$b
dan mulai pencarian kami berikutnya.Peringatan: Ini lambat untuk input besar. Bahkan, itu tidak dapat menyelesaikan
50
tes atau lebih tinggi dalam batas waktu 60-an di TIO. Baiklah.sumber
Sekam ,
131110 byteCobalah online!
sumber
Mathematica, 39 byte
Versi 33 byte (tidak valid karena hanya naik ke 65535 prime)
sumber
Python 2 ,
9688 byte- 8 byte Terima kasih kepada @Maltysen
Cobalah online!
sumber
Perl 6 , 63 byte
Cobalah online!
sumber
Mathematica, 37 byte
Function
dengan argumen pertamag
. Mulai dengan2
, terapkan fungsip=NextPrime
berulang kali selamap@#-#<g&
memberiTrue
(jarak antara prime saat ini dan prime berikutnya kurang darig
).sumber
R + gmp, 55 byte
Memanfaatkan fungsi nextprime dari pustaka gmp
sumber
cat(s)
di bagian akhir. Pencetakan tersirat tidak berfungsi dalam program lengkap.Ruby , 61 byte
Cobalah online!
sumber
C =
141109 byte; C ++, D = 141 byte; C #, Java = 143 bytePERINGATAN : ALGORITMA KINERJA RENDAH
Kode ini tidak dapat menghitung celah utama
g(200)
dalam waktu 10 menit. Untukg(100)
itu, dibutuhkan 10 detik (versi C ++)Versi C ++ dan D:
C # dan versi Java:
Versi C, -32 bytes berkat ceilingcat:
Perbedaan antara versi C # / Java dan C / C ++ / D:
!p(n)
<==>p(n)==0
sumber
return 0; return 1
dan menghapus!
sebelumnyap(++n)
d%i==0
dan!(d%i)
bisad%i<0
. Juga, menggunakan sistem template D's solusi di D dapat:T p(T)(T d){for(T i=2;i<=d/2;++i)if(d%i<1)return 0;return 1;}T g(T)(T d){T f=2,n=3;while(n-f<d){f=n;do++n;while(!p(n));}return f;
. (Penghapusan kawat gigi setelahfor
dando
mungkin berlaku untuk C ++ juga)int p(int d){for(int i=2;i<=d/2;++i)if(!(d%i))return 0;return 1;}int g(int d){int f=2,n=3;while(n-f<d){f=n;do++n;while(!p(n));}return f;}
<- yang seharusnya berfungsi untuk versi C ++D,
127125122 bytePERINGATAN: ALGORITMA KINERJA RENDAH !!
Cobalah online!
Bagaimana?
HatsuPointerKun lagi, tapi aku akan melakukan sihir khusus D.
T p(T)(T d)
, dan lebih pendek dari C ++r=d%i++<1||r
, D shenanigans khusus, mungkin bekerja di C / C ++, tapi saya tidak tahu.p(++n)
, sama seperti di atas, tidak yakin apakah itu berfungsi di C / C ++while(p(++n)){}
, di sini kita melihat mengapa D buruk dalam bermain golf, kita tidak bisa menggunakan;
pernyataan kosong.sumber
Perl 6 ,
4137 byteCobalah online!
Penjelasan
sumber
QBIC , 28 byte
Penjelasan
sumber
05AB1E , 9 byte
Cobalah secara online atau verifikasi semua kasus uji . (Test Suite tidak mengandung dua test case terakhir, karena TIO time out untuk itu.)
Karena pertanyaan lain ditutup sebagai duplikat dari pertanyaan ini , saya juga memposting jawaban saya di sini.
Penjelasan:
sumber
Java 8,
9992 byteCobalah online. (Uji kasus terbesar tidak termasuk, karena waktu habis di TIO.)
Penjelasan:
sumber
Tidy , 33 byte
Cobalah online!
Atau, 28 karakter / 34 byte:
{x:({v:⊟v≤-x}↦primes+2)@0@0}
Saya akan menjelaskan hal ini menggunakan ekuivalen, setara ASCII:
sumber
APL (NARS), 36 char, 72 byte
1π adalah fungsi "prime berikutnya"; uji:
sumber