Mempertimbangkan sejumlah prima p , ditulis dalam basis 10. The memori dari p didefinisikan sebagai jumlah bilangan prima yang berbeda ketat kurang dari p yang terkandung sebagai substring dari p .

Tantangan

Diberikan bilangan bulat n -negatif sebagai input, cari p utama terkecil sehingga p memiliki memori n . Artinya, temukan bilangan prima terkecil dengan tepat n bilangan prima yang lebih rendah sebagai substring.

Memasukkan

Input dapat diambil melalui format standar apa pun. Anda harus mendukung input hingga n terbesar sehingga output tidak meluap. Sebagai referensi, 4294967291 adalah prime terbesar dalam 32 bit.

Keluaran

Output dapat ditulis ke STDOUT atau dikembalikan dari suatu fungsi.

Contohnya

Angka 2 memiliki memori 0 karena tidak mengandung bilangan prima yang lebih kecil sebagai substring.

Angka 113 adalah bilangan prima terkecil dengan memori 3. Angka 3, 13, dan 11 adalah satu-satunya substring utama dan tidak ada bilangan prima yang lebih kecil dari 113 berisi tepat 3 bilangan prima sebagai substring.

10 syarat pertama dari urutan, dimulai dengan n = 0, adalah

2, 13, 23, 113, 137, 1237, 1733, 1373, 12373, 11317

Catatan

Ini adalah A079397 di OEIS.

Papan peringkat

var QUESTION_ID=55406,OVERRIDE_USER=20469;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Pyth, 22 byte

f&}TPTqQlf}YPY{sMP.:`T

Demonstrasi , Test Harness

Penjelasan:

f&}TPTqQlf}YPY{sMP.:`T
                          Implicit: Q = eval(input())
f                         Starting at T=1 and counting up, return the first T where
                    `T    repr(T)
                  .:      all substrings
                 P        except T itself
               sM         converted to integers
              {           unique examples only
         f                filter on
          }YPY            Y is in the prime factorization of Y, e.g. Y is prime.
      qQl                 Q == len of the above, that is, T has memory Q,
 &}TPT                    and T is prime, (is in its prime factorization.)

CJam, 33 31 30 byte

1{)__mp*{_mp2$s@s#)*},,easi^}g

Ini adalah program lengkap yang membaca input sebagai argumen baris perintah.

Cobalah online di juru bahasa CJam .

Uji coba

$ time cjam <(echo '1{)__mp*,{_mp2$s@s#)*},,easi^}g') 9
11317
real    0m3.562s
user    0m4.065s
sys     0m0.177s

Bagaimana itu bekerja

1       e# Push I := 1 on the stack.
{       e# Do:
  )__   e#   Increment I and push two copies.
  mp*   e#   Check the last copy for primality and multiply with the first copy.
        e#   This pushes R := I if I is prime and R := 0 if it is composite.
  {     e#   Filter; for each J in [0 ... R-1]:
    _mp e#     Push a copy of J and check for primality.
    2$s e#     Push a copy of I and cast to string.
    @s  e#     Rotate the original J on top of the stack and cast to string.
    #   e#     Find the index (-1 if not found) of the latter in the former.
    )*  e#     Increment the index and multiply it with the result from `mp'.
        e#     This yields 0 iff J is composite or not a subtring of I.
  },    e#   Keep J if the product is non-zero.
  ,     e#   Push the length of the filtered range.
  easi  e#   Cast the array of command-line arguments to string, then to integer.
  ^     e#   XOR it with the length of the filtered range.
}g      e# Repeat while theresult is non-zero.

CJam, 40 byte

li2sa{_)\{1$\#)},,3$-}{i{)_mp!}gsa+}w]W=

Cobalah online

Saya yakin ini datang sebagai kejutan besar, tetapi sebenarnya lebih lama dari solusi yang diposting Dennis. Yah, tidak juga, karena aku sendiri tidak punya harapan yang terlalu tinggi. Tapi saya tetap ingin mencobanya. Dan karena itu bekerja, terlihat cukup masuk akal bagi saya, dan saya percaya itu cukup berbeda untuk setidaknya menjadi minat, saya pikir saya akan tetap mempostingnya.

Ide dasar di sini adalah bahwa saya membangun daftar bilangan prima dalam satu lingkaran, menambahkan bilangan prima berikutnya yang lebih besar ke daftar di setiap langkah. Untuk memeriksa penghentian, saya menghitung berapa banyak elemen selain elemen terakhir dalam daftar adalah substring dari elemen terakhir. Jika jumlah ini sama dengan input n, kita sudah selesai.

Penjelasan:

li    Get input and convert to integer.
2sa   Seed list of primes with ["2"]. The primes are stored as strings to make
      the later substring search more streamlined.
{     Start of while loop condition.
  _   Copy list of primes.
  )     Pop off last prime from list.
  \     Swap remaining list to top.
  {     Start of filter block for substring matches with all smaller primes.
    1$    Copy test prime to top.
    \     Swap the smaller prime to top to get correct order for substring search.
    #     Search.
    )     Increment to get truthy value (Search returns -1 if not found).
  },    End of filter. We have a list of smaller primes that are substrings now.
  ,     Count list entries.
  3$    Copy input n to top.
  -     Subtract the two for comparison. If they are different, continue loop.
}     End of while loop condition.
{     Start of while loop body. We need to generate the next prime.
  i     The largest prime so far is still on the stack, but as string.
        Convert it to integer.
  {     Start of loop for prime candidates.
    )     Increment current candidate value.
    _mp   Check if it is prime.
    !     Negate, loop needs to continue if it is not a prime.
  }g    End loop for prime candidates. On exit, next prime is found.
  sa+   Convert it to string, and add it to list of primes.
}w    End of while loop body.
]W=   Solution is at top of stack. Discard other stack entries.

Pyth - 25 byte

Filter bersarang, bagian dalam untuk menghitung memori, bagian luar untuk mencari yang membutuhkan memori.

f&!tPTqlf&!tPY}`Y`TtStTQ2

Test Suite .

Oktaf / Matlab, 126 byte

function p=f(n)
p=1;t=1;while t
p=p+1;t=~isprime(p)|sum(arrayfun(@(x)any(strfind(num2str(p),num2str(x))),primes(p)))~=n+1;end

Cobalah online

JavaScript ES6, 106 byte

n=>{for(a=[],i=2;a.filter(c=>(''+i).search(c)+1).length-n-1;a.push(i))while(!a.every(c=>i%c))i++;return i}

Berikut adalah versi yang tidak dikoleksi dengan penjelasan:

n=>{
  /**
   * a = list of primes
   * i = current integer
   * Iterate until number of members in a that are substring of i == n-1
   * After each iteration push the current value of i onto a
   */
  for(a=[],i=2; a.filter(c=>(''+i).search(c)+1).length-n-1; a.push(i)) {
    // Iterate until no member of a exactly divides i and increment i per iteration
    while(!a.every(c=>i%c)) i++;
  }
  return i;
}

Tentu saja ini menjadi sangat lambat dengan agak cepat. Namun OP telah menyatakan tidak ada batasan waktu.

Brachylog (2), 12 byte, tantangan tanggal bahasa

~{ṗ≜{sṗ}ᵘkl}

Cobalah online!

Ini sebelumnya 13 byte, menggunakan ᶠd , tetapi yang sekarang telah diberi singkatan ᵘ, memotongnya menjadi 12. Karena bahasa yang memposting tanggal tantangan tetap, dan fitur adalah salah satu yang tidak ditambahkan untuk tantangan ini pada khususnya, saya mungkin juga Gunakan.

Seperti biasa di Brachylog, ini adalah fungsi, bukan program lengkap.

Penjelasan

~{ṗ≜{sṗ}ᵘkl}
~{         }  Find a value for which the following is true:
  ṗ             The value is prime;
   ≜            (evaluation strategy hint; avoids an infinite loop)
    {  }ᵘ       The set of unique
     sṗ         substrings which are prime
          l     has a length equal to {the input}
         k      when one element is removed.

Ini memberi kita prime terkecil dengan properti yang kita inginkan, karena ≜memeriksa nilai mendekati 0 terlebih dahulu.

Python 2, 163 154 Bytes

Aku terlalu lelah untuk bermain golf .. Semoga ketika aku bangun besok aku bisa memperbaikinya.

p=lambda n:all(n%x for x in range(2,n))
g=input()
s=2
while not(p(s)and len([l for l in[str(x)for x in range(2,s)if p(x)]if l in str(s)])==g):s+=1
print s

Julia, 86 byte

n->for i=1:~0>>>1 isprime(i)&&sum(j->contains("$i","$j"),primes(i-1))==n&&return i;end

Praktis cukup jelas. Ulangi semua bilangan bulat positif, dan setiap kali prime ditemukan, jumlah array boolean yang menunjukkan apakah himpunan bilangan prima kurang dari yang sekarang adalah substring dari yang sekarang. Jika menemukan satu dengan jumlah kecocokan yang diperlukan, kembalikan nilai itu.

Waktu berjalan menjadi lambat untuk n = 11, dan kemungkinan untuk sebagian besar nilai lebih tinggi dari 11 - khususnya, di laptop saya, n = 11 membutuhkan waktu sekitar 33 detik.

Haskell, 149 147 144 byte

(127 byte tidak termasuk importdeklarasi).

import Data.List
i x=x`elem`nubBy(((>1).).gcd)[2..x]
f n=[p|p<-[2..],i p,n==length(nub[x|x<-[read b|a<-tails$show p,b<-tail$inits a],i x])-1]!!0

Prelude Data.List> map f [0..20]
[2,13,23,113,137,1237,1733,1373,12373,11317,23719, Terganggu.

Output di atas diproduksi dengan definisi yang lebih panjang

i x=and$[x>1]++[rem x n>0|n<-[2..x-1]]

Baru, 3 karakter lebih pendek, definisi jauh lebih lambat, saya hanya bisa mendapatkan 5 angka pertama dalam urutan sebelum kehilangan kesabaran dan batal.

Haskell , 119 118 byte

p x=all((>0).mod x)[2..x-1]
f n=[y|y<-[2..],p y,n==sum[1|x<-[2..y-1],p x,elem(show x)$words=<<(mapM(:" ")$show y)]]!!0

Cobalah online! Penggunaan: f 3hasil 113.

PHP, 124 byte

for($p=1;;){for($i=$c=0;$i-1;)for($i=++$p;$p%--$i;);$m[]=$p;foreach($m as$q)$c+=!!strstr($p,"$q");$c-1-$argv[1]?:die("$p");}

mengambil input dari argumen baris perintah; jalankan bersama-r .

kerusakan

for($p=1;;)
{
    for($i=$c=0;$i-1;)for($i=++$p;$p%--$i;);    // find prime $p
    $m[]=$p;                                    // remember that prime
    foreach($m as$q)$c+=!!strstr($p,"$q");      // count memory primes
    $c-1-$argv[1]?:die("$p");                   // if memory==N, exit
}

Python 2 , 108 byte

f=lambda n,x=2:n-sum(all(j%k for j in(i,x)for k in range(2,j))for i in range(2,x)if`i`in`x`)and f(n,x+1)or x

Cobalah online!