Solitude of Prime Numbers

24

Baru-baru ini saya membaca novel "The Solitude of Prime Numbers" di mana karakter utama agak dibandingkan dengan bilangan prima kembar (" selalu bersama, tetapi tidak pernah menyentuh ").

Sebuah prima kembar adalah bilangan prima yang baik 2 kurang atau lebih dari 2 nomor lainnya prima -misalnya, pasangan prima kembar (41, 43). Dengan kata lain, prime kembar adalah prime yang memiliki kesenjangan utama dua. Terkadang istilah twin prime digunakan untuk sepasang bilangan prima kembar; nama alternatif untuk ini adalah kembar prima atau pasangan prima. Wikipedia

Meskipun saya tidak terlalu menyukai novel yang menyedihkan itu, dan karena saya telah jatuh ke dalam PPCG belakangan ini, hal itu menimbulkan pertanyaan di benak saya ...

Tugas:

Dengan bilangan bulat positif N> 4, temukan bilangan prima yang kesepian ( bilangan prima terisolasi AKA ) di antara pasangan terdekat bilangan prima kembar .

Harap dicatat bahwa dalam hal ini dengan istilah bilangan prima kesepian , maksud saya semua bilangan prima yang bukan bilangan prima kembar dan antara pasangan bilangan prima kembar . Itu sebabnya N> 4 karena dua pasangan pertama dari bilangan prima adalah (3, 5) dan (5, 7).

Contoh:

  1. N = 90.
  2. Temukan dua pasangan pertama kembar prima <N dan> N. Mereka adalah: (71, 73) dan (101, 103).
  3. Temukan bilangan prima kesepian dalam kisaran> 73 dan <101.
  4. Mereka adalah: 79, 83, 89, 97.

Kasus khusus:

  • Jika N ada di antara dua bilangan prima kembar, temukan pasangan terdekat bilangan prima kembar> N + 1 dan <N-1. Contoh: N = 72, cari pasangan prima kembar terdekat> 73 dan <71 kemudian kecualikan dari daftar 71 dan 73 karena mereka bukan primes kesepian . Jadi untuk N = 72 hasil yang diharapkan adalah: 67, 71 , 73 , 79, 83, 89, 97
  • Jika N termasuk pasangan prima kembar, misalnya N = 73, pasangan terdekat prima kembar adalah (71, 73) dan (101, 103). Jika N = 71, pasangan terdekat dari prima kembar adalah (59, 61) dan (71, 73).

Kasus uji:

N = 70   >  Lonely primes are:  67
N = 71   >  Lonely primes are:  67
N = 72   >  Lonely primes are:  67, 79, 83, 89, 97 (not the twins 71 and 73)
N = 73   >  Lonely primes are:  79, 83, 89, 97 
N = 90   >  Lonely primes are:  79, 83, 89, 97
N = 201  >  Lonely primes are:  211, 223
N = 499  >  Lonely primes are:  467, 479, 487, 491, 499, 503, 509

Aturan:

  • Tulis program atau fungsi lengkap yang akan mengambil angka N dari input standar.
  • Keluarkan daftar primes kesepian dalam format yang dapat dibaca sebagai csv, daftar, array, dll.
  • Kode terpendek menang.
  • Harap sertakan (bila mungkin) biola daring yang dapat diuji.
Mario
sumber
4
Apa output yang diharapkan untuk input seperti 71, 72 atau 73?
Martin Ender
1
Lonely Prime AKA Prime Terisolasi
Digital Trauma
@ MartinEnder Saya memperpanjang pertanyaan saya dengan kasus khusus. Terimakasih atas klarifikasinya.
Mario
1
Saya menemukan kasus-kasus khusus sedikit merusak tantangan (dan ditambahkan ketika beberapa jawaban sudah diposting)
Luis Mendo
1
@ JonathanAllan Ya, Anda dapat mempertimbangkan N> 4 karena dua pasangan pertama dari bilangan prima kembar adalah (3, 5) dan (5, 7). Saya menambahkan spesifikasi untuk memperjelas semua orang.
Mario

Jawaban:

2

Sebenarnya, 47 byte

Solusi ini berkaitan dengan kasus di mana nberada di antara dua bilangan prima kembar, dengan memeriksa apakah batas bawah adalah lebih besar dari sepasang bilangan prima kembar (menghilangkan bilangan prima kembar di sebelah kiri kita dari menjadi batas bawah kita) dan jika batas atas adalah yang lebih kecil dari sepasang bilangan prima kembar (menghilangkan bilangan prima kembar di sebelah kanan kita agar tidak menjadi batas atas kita). Untuk mencegah bilangan prima kembar dari dimasukkan dalam jangkauan kami setelah kami memiliki batas bawah dan atas, kita perlu menghapus bilangan prima di pmana p-2OR p+2adalah prima, maka OR logis dan negate dalam kode.

Ini agak panjang dan mungkin bisa bermain golf lebih lanjut. Saran bermain golf diterima. Cobalah online!

╗1`╜+;⌐p@p&`╓F╜+1`╜-;¬p@p&`╓F╜-x`;;¬p@⌐p|Y@p&`░

Tidak melakukanolf

╗         Store implicit input n in register 0.

1`...`╓   Get the first value x for which the following function f returns a truthy value.
  ╜         Push n from register 0.
  +         Add x to n.
  ;⌐        Duplicate n+x and add 2 to a copy of n+x.
  p         Check if n+x+2 is prime.
  @p        Swap n+x to TOS and check if n+x is prime.
  &         Logical AND the two results.
F         Push the first (and only) result of previous filtering
╜+        Add that result to n to get the upper bound for our solitude.

1`...`╓   Get the first value x for which the following function f returns a truthy value.
  ╜         Push n from register 0.
  -         Subtract x from n.
  ;¬        Duplicate n-x and subtract 2 from a copy of n-x.
  p         Check if n-x-2 is prime.
  @p        Swap n-x to TOS and check if n-x is prime.
  &         Logical AND the two results.
F         Push the first (and only) result of previous filtering.
╜-        Subtract that result from n to get the lower bound for our solitude.

x`...`░   Push values of the range [a...b] where f returns a truthy value. Variable m.
  ;;        Duplicate m twice.
  ¬p        Check if m-2 is prime.
  @⌐p       Check if m+2 is prime. 
  |Y        Logical OR the results and negate.
             This eliminates any numbers with neighboring primes.
  @p        Check if m is prime.
  &         Logical AND primality_check(m) and the previous negation.
             This keeps every other prime number in the range.
Sherlock9
sumber
Saya tidak mendapatkan output yang diharapkan 23saat input 24diberikan. Batas utama kembar harus 17 / 19dan 29 / 31, dan 23merupakan prime terisolasi dalam kisaran 19 .. 29.
AdmBorkBork
@TimmyD Oh untuk cinta esolang. Entah bug mana yang pmengatakan 25prima belum diperbaiki, atau Dennis belum menarik Sebenarnya sejak perbaikan bug. Biarkan aku periksa.
Sherlock9
@TimmyD Karena perbaikan bug sudah selesai, jawaban ini masih valid karena interpreter utama berfungsi. Hanya saja penerjemah online, Try It Online, belum diperbarui. Sejak itu telah diperbarui dan TIO harus berfungsi sekarang.
Sherlock9
Yap - terima kasih atas penjelasannya!
AdmBorkBork
8

PowerShell v2 +, 237 149 147 231 216 181 174 169 166 byte

param($n)filter f($a){'1'*$a-match'^(?!(..+)\1+$)..'}for($i=$n;!((f $i)-and(f($i+2)))){$i++}for(){if(f(--$i)){if((f($i-2))-or(f($i+2))){if($i-lt$n-1){exit}}else{$i}}}

Mengambil input $n. Menentukan fungsi baru fsebagai fungsi prime regex (di sini mengembalikan Boolean jika inputnya prima atau tidak).

Bagian berikutnya ditetapkan $isama dengan $n, kemudian loop ke atas sampai kita menemukan setengah bagian bawah dari pasangan utama kembar kita. Misalnya, untuk input 90, ini berhenti di $i=101.

Kemudian, kita loop dari batas atas ke bawah. Saya tahu, ini kelihatannya seperti infinite loop, tetapi akhirnya akan berakhir.

Jika jumlah saat ini adalah perdana ( f(--$i)), tapi yang +/- 2 tidak prima, kita tambahkan $ike pipa. Namun, jika itu +/- 2adalah prime, kami memeriksa apakah kami lebih rendah dari $n-1(yaitu, untuk memperhitungkan situasi ketika itu di dalam pasangan prime kembar), pada titik mana kami exit. Pada penyelesaian program, pipa dicetak ke layar melalui implisit Write-Output.

NB - Karena struktur pengulangan, mencetak bilangan prima dengan urutan menurun. OP telah mengklarifikasi tidak apa-apa.

Contohnya

Keluaran di sini dipisahkan dengan ruang, karena itulah metode stringifikasi default untuk array.

PS C:\Tools\Scripts\golfing> 70,71,72,73,90,201,499,982|%{"$_ --> "+(.\the-solitude-of-prime-numbers.ps1 $_)}
70 --> 67
71 --> 67
72 --> 97 89 83 79 67
73 --> 97 89 83 79
90 --> 97 89 83 79
201 --> 223 211
499 --> 509 503 499 491 487 479 467
982 --> 1013 1009 997 991 983 977 971 967 953 947 941 937 929 919 911 907 887
AdmBorkBork
sumber
4

Haskell, 105 byte

p x=all((>0).mod x)[2..x-1]
a%x=until(\z->p z&&p(z+2*a))(+a)x
f n=[x|x<-[(-1)%n+1..1%n-1],p x,1%x>x,(-1)%x<x]

Cobalah secara Online

Damien
sumber
3

JavaScript, 186 183 168 158 Bytes

// solution:
function d(d){function p(n){for(i=n;n%--i;);return!--i}u=d;for(;!p(d--)||!p(--d););for(;!p(u++)||!p(++u););for(;++d<u;)if(p(d)&&!p(d-2)&&!p(d+2))console.log(d)}

// runnable test cases:
console.info('Test ' + 70);
d(70);
console.info('Test ' + 71);
d(71);
console.info('Test ' + 72);
d(72);
console.info('Test ' + 73);
d(73);
console.info('Test ' + 90);
d(90);
console.info('Test ' + 201);
d(201);
console.info('Test ' + 499);
d(499);

pengguna470370
sumber
Selamat datang di PPCG! Jawaban pertama yang bagus.
AdmBorkBork
2

PHP, 207 byte

47 54 byte untuk is_primefungsi yang tidak dimiliki PHP. Saya akan mengalahkan Mathematica tanpa itu. :-D

function p($n){for($i=$n>1?$n:4;$n%--$i;);return$i<2;}if(p($n=$argv[1])&p($n+2)|$z=p($n-1)&p($n+1))$n-=2;for($n|=1;!p($n)|!p($n-2);$n--);for($z++;$z--;$n+=2)for(;$n+=2;)if(p($n)){if(p($n+2))break;echo"$n,";}

jalankan bersama -r. mencetak koma jejak.

kerusakan

// is_prime function:
// loops from $n-1 down to 1, breaks if it finds a divisor.
// returns true if divisor is <2 (==1)
// special case $n==1: initialize $i=4 to prevent warnings
function p($n){for($i=$n>1?$n:4;$n%--$i;);return$i<2;}

// is $n between primes?
if($z=p(1+$n=$argv[1])&p($n-1)) // set $z to go to the _second_ twin pair above
    $n-=2;
// no:
else
    if(p($n)&p($n+2))$n-=2;     // $n is part of the upper pair
    // p($n)&p($n-2):           // $n is part of the lower pair
    // else:                    // this is a lonely (isolated) prime

// 1. find closest twins <=$n
for($n|=1;!p($n)|!p($n-2);$n--);

// 2. list primes until the next twin primes
L:
for(;$n+=2;)if(p($n))
    if(p($n+2))break;       // next twin primes found: break loop
    else echo"$n,";         // isolated prime: print

// 3. if ($z) repeat (once)
$n+=2;  // skip twin pair
if($z--)goto L;

Catatan :

The is_primefungsi benar-benar kembali trueuntuk $n<2; tapi setidaknya itu tidak menghasilkan peringatan. Masukkan $n=sebelum $n>1untuk memperbaikinya.

Titus
sumber
php.net/manual/en/function.gmp-nextprime.php dapatkah perpustakaan ini membantu?
Jörg Hülsermann
@ JörgHülsermann: Jika akan memberikan setidaknya 11 byte, jika gmp akan berada di instalasi standar. Cobalah.
Titus
1

Mathematica, 169 157 byte

Select[PrimeQ]@Sort@Flatten@{If[q@#,0,#],Most@NestWhileList[i-=2;#+i&,#,!q@#&]&/@(i=3;q=PrimeQ@#&&Or@@PrimeQ[{2,-2}+#]&;#+{1,-1}(1+Boole@PrimeQ[{1,-1}+#]))}&
JungHwan Min
sumber
1

Racket 228 byte

(λ(n)(let*((t 0)(lr(λ(l i)(list-ref l i)))(pl(drop(reverse(for/list((i(in-naturals))#:when(prime? i)#:final(and(> i n)
(= 2(- i t))))(set! t i)i))2)))(for/list((i(length pl))#:break(= 2(-(lr pl i)(lr pl(add1 i)))))(lr pl i))))

Kerugian dari versi ini adalah ia menemukan semua bilangan prima hingga N dan bukan hanya yang di sekitar N.

Versi tidak disatukan:

(define (f n)
  (let* ((t 0)
         (lr (λ(l i) (list-ref l i)))
         (pl (drop(reverse  
                   (for/list ((i (in-naturals))
                              #:when (prime? i)
                              #:final (and
                                       (> i n)
                                       (= 2 (- i t))))
                     (set! t i)
                     i)) 2)))
    (for/list ((i (length pl))
               #:break (= 2 (- (lr pl i) (lr pl (add1 i)))) )
      (lr pl i)))
)

Pengujian:

(f 90)

Keluaran:

'(97 89 83 79)
juga
sumber
1

Racket 245 byte

(λ(n)(let((pl(reverse(let lp((n n)(t 0)(ol '()))(set! t(prev-prime n))(if(and(>(length ol)0)
(= 2(-(car ol)t)))(cdr ol)(lp t 0(cons t ol)))))))(let lq((n n)(t 0)(ol pl))(set! t(next-prime n))
(if(= 2(- t(car ol)))(cdr ol)(lq t 0(cons t ol))))))

Versi tidak disatukan:

(require math)
(define f
  (lambda(n)
    (let ((pl 
           (reverse
            (let loop ((n n) (t 0) (ol '()))
              (set! t (prev-prime n))
              (if (and
                   (> (length ol) 0)
                   (= 2 (- (car ol) t)))
                  (cdr ol)
                  (loop t 0 (cons t ol)))))))
      (let loop2 ((n n) (t 0) (ol pl))
        (set! t (next-prime n))
        (if (= 2 (- t (car ol)))
            (cdr ol)
            (loop2 t 0 (cons t ol))))))
  )

(f 90)

Keluaran:

'(97 89 83 79)
juga
sumber
1

Python 2.7: 160 byte

t=lambda n:all(n%d for d in range(2,n))
def l(n):
 i=n
 while t(i)*t(i+2)-1:i+=1
 while t(n)*t(n-2)-1:n-=1
 print[x for x in range(n,i)if t(x)&~(t(x-2)|t(x+2))]

saran dipersilahkan :)

Harun
sumber