Temukan celah utama

27

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 natau lebih besar.

Sebagai contoh, untuk input 4output 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
Luis Mendo
sumber
Terkait
Luis Mendo
Maksud Anda maksud qp benar?
Erik the Outgolfer
@EriktheOutgolfer Ya; dikoreksi, terima kasih!
Luis Mendo
OEIS A104138
Luis Mendo
OEIS A002386 (Terkait)
Stephen

Jawaban:

3

Gaia , 6 byte

zṅọ⊃∆ṇ

Ini sangat tidak efisien ( 16test case membutuhkan lebih dari satu jam untuk menghitung pada mesin saya).

Cobalah online!

Penjelasan

Urutannya tampaknya memiliki properti yang a (n) <= 2 ^ n .

z       Push 2^input.
 ṅ      Get the first 2^input prime numbers.
  ọ     Get the deltas of the list.
   ⊃∆   Find the index of the first that is greater than or equal to the input.
     ṇ  Push the index-th prime number.
Kucing Bisnis
sumber
9

Jelly , 10, 9, 8 10 byte

Æn_$:ð1#»2

Cobalah online!

Dua byte disimpan berkat @Dennis! (dan kemudian ditambahkan kembali karena kasus tepi)

Penjelasan:

Æn          #   The next prime after 'P'
  _$        #   Minus 'P'
    :       #   Divided by 'N'
            #
            # This will give a falsy value unless the distance to the next prime is >= N
            #
     ð      # Treat all of that as a single dyad (fucntion with two arguments). 
            # We'll call it D(P, N)
            #
      1#    # Find the first 'P' where D(P, input()) is truthy
        »2  # Return the maximum of that result and 2
DJMcMayhem
sumber
Apakah kita tahu pasti bahwa hasilnya akan selalu lebih besar dari atau sama dengan input? ( #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) dengan
Jonathan Allan
5
Postulat @JonathanAllan Bertrand menyiratkan bahwa celah prima benar-benar kurang dari prima itu sendiri.
Dennis
@Dennis brilian terima kasih banyak! TMYK ...
Jonathan Allan
4

Mathematica, 30 byte

2//.x_ /;NextPrime@x-x<#:>x+1&

Cobalah online!

Mathematica, 35 byte

(t=2;While[NextPrime@t-t<#,t++];t)&

Cobalah online!

Mathematica, 77 byte

Prime@Min@Position[s=Differences@Prime@Range[(r=#)^3+1],#&@@Select[s,#>=r&]]&
J42161217
sumber
Pintar pintar ... Anda bahkan tidak perlu memastikan keduanya pdan qprima ... Kode pertama tampaknya tidak valid, karena hanya naik hingga 65535 kecuali Anda secara eksplisit memberi makan argumen MaxIterations.
JungHwan Min
Juga, -2 byte untuk versi 35-byte:(For[t=2,NextPrime@t-t<#,t++];t)&
JungHwan Min
4

Haskell , 106 102 93 77 73 72 byte

Ini 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!

f n=[x|(y,x)<-zip=<<tail$[n|n<-[2..],all((>0).rem n)[2..n-1]],y-x>=n]!!0

Cobalah online!

cacat
sumber
Tentu saja ada beberapa keajaiban monad, terima kasih :)
flawr
zip=<<tail$[...]menghemat satu byte.
Zgarb
"Ini menghasilkan daftar bilangan prima yang tak terbatas terlebih dahulu, lalu ...": yah, maka seharusnya tidak pernah terjadi? (yaitu, itu hanya akan terjadi setelah waktu yang sangat lama, waktu untuk "menghasilkan pertama" secara prosedural daftar bilangan prima yang tak terbatas)
Olivier Dulac
1
Haskell menggunakan evaluasi malas, sehingga hanya banyak entri dari daftar yang dihasilkan seperti yang sebenarnya digunakan. Jadi bilangan prima tersebut dihasilkan sampai pada titik di mana kita benar-benar menemukan poin. Jika Anda mencobanya, Anda akan melihat bahwa untuk apa pun nitu akan berhenti setelah waktu yang terbatas :) (Haskell bukan prosedural, tetapi bahasa fungsional dengan evaluasi malas.)
flawr
1
Yah itu adalah daftar yang tak terbatas, menurut definisi itu tidak memiliki tujuan. Apa yang saya jelaskan hanya apa yang terjadi di bawah tenda di penerjemah biasa, tetapi itu tidak ditentukan sebagai bagian dari bahasa sehingga Anda tidak bisa mengatakan itu!
flawr
3

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.

f&P_T<tQ-fP_Yh

Test Suite .

Maltysen
sumber
3

PowerShell , 97 96 91 byte

param($n)for($a=$b=2){for(;'1'*++$b-match'^(?!(..+)\1+$)..'){if($b-$a-ge$n){$a;exit}$a=$b}}

Cobalah online!

Mengambil input $n, set $adan $bsama dengan 2, lalu memasuki forloop tak terbatas . Di dalam, kita teruskan $bsampai kita mencapai prime berikutnya . Kemudian kami memeriksa apakah $b-$a(yaitu kesenjangan) adalah -gkualifikasi atau euntuk $n. Jika ya, kami output $adan exit. Kalau tidak, kami menetapkan $auntuk menjadi $bdan meningkat $bdan mulai pencarian kami berikutnya.

Peringatan: Ini lambat untuk input besar. Bahkan, itu tidak dapat menyelesaikan 50tes atau lebih tinggi dalam batas waktu 60-an di TIO. Baiklah.

AdmBorkBork
sumber
3

Sekam , 13 11 10 byte

´ȯ!V≥⁰Ẋ-İp

Cobalah online!

´       İp  -- with the primes
 ȯ!         -- get the value at position
      Ẋ-    -- where the difference of the current and next prime
   V≥⁰      -- is greater or equal than the input N
ბიმო
sumber
3

Mathematica, 39 byte

(For[i=2;p=NextPrime,i+#>p@i,i=p@i];i)&
(* or *)
(For[i=1;p=Prime,p@i+++#>p@i,];p[i-1])&

Versi 33 byte (tidak valid karena hanya naik ke 65535 prime)

p=NextPrime;2//.i_/;p@i-i<#:>p@i&
JungHwan Min
sumber
2

Python 2 , 96 88 byte

- 8 byte Terima kasih kepada @Maltysen

n,p,r=input(),3,[2]
while p-r[-1]<n:r+=[p]*all(p%i for i in range(2,p));p+=1
print r[-1]

Cobalah online!

officialaimm
sumber
1
menyimpan banyak byte: repl.it/JwBe
Maltysen
2

Perl 6 , 63 byte

->\d{(grep &is-prime,^∞).rotor(2=>-1).first({-d>=[-] $_})[0]}

Cobalah online!

Sean
sumber
2

Mathematica, 37 byte

gNestWhile[p=NextPrime,2,p@#-#<g&]

Functiondengan argumen pertama g. Mulai dengan 2, terapkan fungsi p=NextPrimeberulang kali selama p@#-#<g&memberi True(jarak antara prime saat ini dan prime berikutnya kurang dari g).

ngenisis
sumber
2

R + gmp, 55 byte

Memanfaatkan fungsi nextprime dari pustaka gmp

s=2;n=scan();while((x=gmp::nextprime(s))-s<n)s=x;cat(s)
MickyT
sumber
Anda harus menambahkan cat(s)di bagian akhir. Pencetakan tersirat tidak berfungsi dalam program lengkap.
JAD
2

C = 141 109 byte; C ++, D = 141 byte; C #, Java = 143 byte

PERINGATAN : ALGORITMA KINERJA RENDAH

Kode ini tidak dapat menghitung celah utama g(200)dalam waktu 10 menit. Untuk g(100)itu, dibutuhkan 10 detik (versi C ++)

Versi C ++ dan D:

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;}

C # dan versi Java:

int p(int d){for(int i=2;i<=d/2;++i){if(d%i==0)return 0;}return 1;}int g(int d){int f=2,n=3;while(n-f<d){f=n;do{++n;}while(p(n)==0);}return f;}

Versi C, -32 bytes berkat ceilingcat:

i;p(d){for(i=2;d/2/i;)if(!(d%i++))return 0;return 1;}f;n;g(d){for(f=2,n=3;n-f<d;)for(f=n;!p(++n););return f;}

Perbedaan antara versi C # / Java dan C / C ++ / D: !p(n)<==>p(n)==0

HatsuPointerKun
sumber
Dapat membalik return 0; return 1dan menghapus !sebelumnyap(++n)
ceilingcat
d%i==0dan !(d%i)bisa d%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 setelah fordan domungkin berlaku untuk C ++ juga)
Zacharý
Saya memposting versi D yang terpisah, yang menggunakan trik khusus D yang tidak dapat ditemukan di C / C ++ / C # / Java.
Zacharý
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 ++
Zacharý
2

D, 127 125 122 byte

PERINGATAN: ALGORITMA KINERJA RENDAH !!

T p(T)(T d){T r;for(T i=2;i<=d/2;)r=d%i++<1||r;return r;}T g(T)(T d){T f=2,n=3;while(n-f<d){f=n;while(p(++n)){}}return f;}

Cobalah online!

Bagaimana?

HatsuPointerKun lagi, tapi aku akan melakukan sihir khusus D.

  • Sistem template dapat menyimpulkan tipe 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.
Zacharý
sumber
2

Perl 6 , 41 37 byte

{+(1...(^$_+*)>>.is-prime eqv!<<^$_)}

Cobalah online!

Penjelasan

{                                   }  # Block taking n as $_
   1...   # Sequence 1,2,... until
       (^$_+*)  # Range [i,i+n)
              >>.is-prime  # is-prime for each
                          eqv!<<^$_  # Equals (True,False,False,False,...)?
 +(                                )  # Length of sequence
nwellnhof
sumber
1

QBIC , 28 byte

{~µs||~s-r>=:|_Xr\r=s]]s=s+1

Penjelasan

{         DO
~µs||     IF s is prime THEN (note, s starts as 3)
~s-r>=:   IF the gap between s (current prime) and r (prev prime) is big enough
|_Xr      THEN QUIT, printing prev prime r
\r=s      ELSE (gap too small, but s is prime), set r to prime s
]]        END IF x2, leaving us in the WHILE
s=s+1     increment s, retest for primality ...
steenbergh
sumber
1

05AB1E , 9 byte

∞<ØD¥I@Ïн

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:

           # Get an infinite list in the range [1, ...]
 <          # Decrease it by one to make it in the range [0, ...]
  Ø         # Get for each the (0-indexed) n'th prime: [2,3,5,7,11,...]
   D        # Duplicate this list of primes
    ¥       # Get all deltas (difference between each pair): [1,2,2,4,2,...]
     I@     # Check for each if they are larger than or equal to the input
            #  i.e. 4 → [0,0,0,1,0,1,0,1,1,0,...]
       Ï    # Only keep the truthy values of the prime-list
            #  → [23,31,47,53,61,...]
        н   # And keep only the first item (which is output implicitly)
            #  → 23
Kevin Cruijssen
sumber
1

Java 8, 99 92 byte

n->{int a=2,b=3,f,k;for(;b-a<n;)for(f=0,a=b;f<2;)for(f=++b,k=2;k<f;)f=f%k++<1?0:f;return a;}

Cobalah online. (Uji kasus terbesar tidak termasuk, karena waktu habis di TIO.)

Penjelasan:

n->{               // Method with integer as both parameter and return-type
  int a=2,b=3,     //  Prime-pair `a,b`, starting at 2,3
      f,           //  Prime-checker flag `f`, starting uninitialized
      k;           //  Temp integer, starting uninitialized
  for(;b-a         //  Loop as long as the difference between the current pair of primes
          <n;)     //  is smaller than the input
    for(f=0,       //   (Re)set the prime-checker flag to 0
        a=b;       //   Replace `a` with `b`, since we're about to search for the next prime-pair
        f<2;)      //   Inner loop as long as the prime-checker flag is still 0 (or 1)
                   //   (which means the new `b` is not a prime)
      for(f=++b,   //    Increase `b` by 1 first, and set this value to the prime-checker flag
          k=2;     //    Set `k` to 2
          k<f;)    //    Inner loop as long as `k` is still smaller than the prime-checker flag
        f=         //     Change the prime-checker flag to:
          f%k++<1? //      If the prime-checker flag is divisible by `k`
           0       //       Set the prime-checker flag to 0
          :        //      Else:
           f;      //       Leave it unchanged
                   //    (If any integer `k` in the range [2, `b`) can evenly divide `b`,
                   //     the prime-checker flag becomes 0 and the loop stops)
  return a;}       //  And finally after all the nested loops, return `a` as result
Kevin Cruijssen
sumber
1

Tidy , 33 byte

{x:({v:⊟v<=-x}↦primes+2)@0@0}

Cobalah online!

Atau, 28 karakter / 34 byte: {x:({v:⊟v≤-x}↦primes+2)@0@0}

Saya akan menjelaskan hal ini menggunakan ekuivalen, setara ASCII:

{x:({v:(-)over v<=-x}from primes+2)@0@0}
{x:                                    }    lambda w/ parameter `x`
                          primes+2          overlapping pairs of primes
                                            [[2, 3], [3, 5], [5, 7], ...]
    {v:             }from                   select prime pairs `v = [a, b]`...
       (-)over v                            ...where `a` - `b`...
                <=-x                        is <= `x`
   (                              )@0@0     select the first element of the first pair
Conor O'Brien
sumber
1

APL (NARS), 36 char, 72 byte

∇r←h w;k
r←2
→0×⍳w≤r-⍨k←1πr⋄r←k⋄→2
∇

1π adalah fungsi "prime berikutnya"; uji:

  h¨1 2 3 4 6 10 16 17 18 30 50 100 200
2 3 7 7 23 113 523 523 523 1327 19609 370261 20831323  
RosLuP
sumber