Dua bilangan prima didefinisikan sebagai bilangan prima kembar jika keduanya berbeda dua. Sebagai contoh, 3 dan 5 adalah bilangan prima kembar seperti 29 dan 31.

Tulis sebuah program yang menemukan pasangan ke-2 dari bilangan prima kembar (di mana n berasal dari STDIN) dan mencetaknya pada STDOUT, dipisahkan dengan koma dan spasi. Ini kode-golf, jadi kode terpendek menang.

Input sampel:

3

Output sampel:

11, 13

Haskell 118

main=putStrLn.(!!)[show n++", "++show(n+2)|n<-[2..],all((>0).rem n)[2..n-1],all((>0).rem(n+2))[2..n]].(+)(-1)=<<readLn

Brute-paksa semua bilangan prima kembar dan cetak pasangan ^ke- n .

CJam, 29 26 byte

Y4]{{:)_{mp}/&!}g}q~*", "*

Cobalah online.

Contohnya

$ for i in {1..10}; do cjam twin-primes.cjam <<< $i; echo; done
3, 5
5, 7
11, 13
17, 19
29, 31
41, 43
59, 61
71, 73
101, 103
107, 109

Bagaimana itu bekerja

Y4]        " Push [ 2 4 ].                                                            ";
{          "                                                                          ";
  {        "                                                                          ";
    :)     " Increment each integer in the array.                                     ";
    _      " Duplicate the array.                                                     ";
    {mp}/  " For each integer in the array, push 1 if it's prime and 0 otherwise.     ";
    &!     " Compute the logical NOT of the bitwise AND of the two previous integers. "; 
  }g       " If the result is non-zero, repeat the loop.                              ";
}q~*       " Do the above “N” times, where “N” is the integer read from STDIN.        ";
", "       " Join the array by comma and space.                                       ";

Perl, 101 87

87 karakter, membangun komentar aschepler

$n=pop;$r='^1$|^(11+?)\1+$';($t=1x$s)=~$r||"11t"=~$r||--$n||die"$s, ",$s+2,$/while++$s

101 karakter, jawaban sebelumnya

$n=pop;$r=qr/^1$|^(11+?)\1+$/;(1x$s)!~$r&&(1x($s+2))!~$r&&++$i==$n&&say($s,", ",$s+2)&&exit while++$s

Pemakaian:

$ perl ./twin_primes.pl 10
107, 109

Penjelasan

$n = pop;                 # Pulls twin prime pair counter from @ARGV
$r = qr/^1$|^(11+?)\1+$/; # The money line - a regex that verifies
                          # if a string of 1's has non-prime length

while ( ++$s ) {          # Loop over integers

                          # '&&' short-circuits
    (1 x  $s    ) !~ $r   # Negated regex match evaluates to true if $s is prime
 && (1 x ($s+2) ) !~ $r   # Same for $s + 2
 &&          ++$i == $n   # Counter to control which pair to print
 && say( $s, ", ", $s+2 ) # Print the line
 && exit                  # Terminate program
}

Cara kerja regex non-primitif dijelaskan dalam pertanyaan SO ini .

C: 113

n,c,l;main(i){for(scanf("%d",&n),l=2;n;l=c==i?n-=i==l+2,i:l,i+=2)for(c=2;c<i&&i%c++;);printf("%d, %d\n",l-2,l);}

Contoh dijalankan:

$ for i in $(seq 1 10); do echo $i | ./twinprimes; done
3, 5
5, 7
11, 13
17, 19
29, 31
41, 43
59, 61
71, 73
101, 103
107, 109

Terima kasih atas bantuan dari Dennis, bebe, dan Alchymist.

CJam - 26

1e4,{mp},_2f-&qi(=_2+", "\

Ini berfungsi untuk bilangan prima yang lebih kecil dari 10.000; Anda dapat mengganti 4dengan eksponen yang lebih tinggi untuk angka yang lebih besar (berpotensi hingga 10 ²⁰ ), tetapi program akan semakin lambat dan akan menggunakan lebih banyak memori.

Cobalah di http://cjam.aditsu.net/

Penjelasan:

1e4,menciptakan larik [0 1 2 ... 9999]
{mp},memilih hanya bilangan prima yang
_2f-menyalin larik dan mengurangi 2 dari setiap item yang
&memotong dua larik, sehingga menemukan bilangan prima yang lebih rendah dari setiap pasangan bilangan kembar utama
qimembaca input dan mengkonversi ke integer
(=menyesuaikan b mengindeks dan mendapatkan kembar prima yang sesuai (lebih rendah) dari array
_2+menyalin prima dan menambahkan 2
", "\menempatkan koma dan ruang antara dua bilangan prima

Mathematica - 63 karakter

Print[#-2,", ",#]&@Nest[NestWhile[NextPrime,#,#2-#!=2&,2]&,1,n]

Catatan

Ini sebenarnya implementasi yang agak mudah. Pemendekan menghasilkan hampir tidak ada kebingungan.

NextPrime adalah builtin yang menemukan prime berikutnya setelah angka.

NestWhile[NextPrime,#,#2-#1!=2&,2]& adalah fungsi anonim yang menemukan prime lebih besar dari pasangan prime kembar berikutnya setelah angka.

Nestberlaku nkali fungsi anonim ini .

Print[#-2,", ",#]&adalah fungsi anonim yang mencetak ke stdout sesuai dengan spesifikasi. Sayangnya ini saja membutuhkan 18 karakter dari solusi 63 karakter.

Contoh

In[1]:= Do[                                                                     
         Print[#-2,", ",#]&@Nest[NestWhile[NextPrime,#,#2-#!=2&,2]&,1,n],
         {n, 1, 10}
        ]
3, 5
5, 7
11, 13
17, 19
29, 31
41, 43
59, 61
71, 73
101, 103
107, 109

Pembaruan: Dua karakter dapat disimpan dengan menerapkan kembali solusi CJam ini . Namun, algoritma ini membatasi nilai maksimum n. Cukup ganti Nest...bagian denganIntersection[#,#-2][[5]]&@Prime@Range[999]

Javascript (E6) 92 96

Lebih pendek dan sesuai - gunakan shell spidermonkey untuk membaca stdin / tulis stdout (dengan koma dan spasi). Ia menemukan pasangan 10000 1260989, 1260991 dalam waktu kurang dari satu menit di PC saya
Bisa lebih pendek menggunakan p[n]=o=nbukan p.push(o=n), sehingga p array jarang. Tapi itu cukup lambat, dan saya tidak akan menang untuk panjang kode.

m=readline();for(n=3,o=p=[];m;n+=2)p.every(e=>n%e)&&(m-=n-o<3,p.push(o=n));print(o-2+', '+o)

Untuk mencoba di konsol firefox:

m=prompt();for(n=3,o=p=[];m;n+=2)p.every(e=>n%e)&&(m-=n-o<3,p.push(o=n));alert(o-2+', '+o)

Tidak disatukan

Fungsi yang menemukan semua m kembar pertama (mengembalikan nilai terbesar):

T=m=>{
  for (o=n=3, p=[2], t=[]; !t[m-1]; n+=2)
    p.every(e => n%e) && (n-o-2 ? 0 : t.push(n), p.push(o=n))
  return t
}

Contoh: console.log(T(50))

[5, 7, 13, 19, 31, 43, 61, 73, 103, 109, 139, 151, 181, 193, 199, 229, 241, 271, 283, 313, 349, 421, 433, 463, 523, 571, 601, 619, 643, 661, 811, 823, 829, 859, 883, 1021, 1033, 1051, 1063, 1093, 1153, 1231, 1279, 1291, 1303, 1321, 1429, 1453, 1483, 1489]

Yang terakhir:

L=m=>{
  for (o=n=3,p=[2]; m; n+=2)
    p.every(e => n%e) && (m -= n-o==2, p.push(o=n))
  return o
}

Kemudian, ambil 2 baris itu dan tambahkan IO

m = prompt()
for (o=n=3, p=[2]; m; n+=2)
  p.every(e => n%e) && (m -= n-o==2, p.push(o=n))
alert('o-2+', '+o)

J - 49 60 55 51 byte

Saya memutuskan untuk pergi dengan pendekatan sederhana. Function tmenemukan prime kembar berikutnya yang diberi bilangan prima sebagai input (sekarang ini termasuk dalam ffungsi). Function fmenemukan prime twin ke-n. Ini juga merupakan program aktual pertama yang saya tulis di J.

f=:[:(":,', ',":@+&2)(4&p:(,{~-=2:)])^:_@>:^:(]`2:)

Contoh:

   f 1
3, 5
   f 2
5, 7
   f 3
11, 13
   f 4
17, 19
   f 5
29, 31
   f 100000
18409199, 18409201

Hanya untuk beberapa alis mata, dapatkan versi tanpa ungolfed.

twin =: (4&p:)(($:@[)`(,)@.(=(]+2:)))]
f    =: ((]-2:),])((0:{twin) ^: (]`(2:)))

Penjelasan:

f=:[:(":,', ',":@+&2)(4&p:(,{~-=2:)])^:_@>:^:(]`2:)
                     (4&p:(,{~-=2:)])^:_@>:^:(]`2:)
                                        @>:^:(]`2:)  main loop
                                           ^:(]`2:)  Repeat n times, starting with value of 2
                                        @>:          Add one to the current value and apply to the following function.
                     (4&p:(,{~-=2:)])^:_             Get the next twin prime
                                     ^:_             Recurse until there's no change
                          (,{~-=2:)                  If next prime - current value == 2, return current value, otherwise the next prime.
                      4&p:                           Get the next prime
     (":,', ',":@+&2)                                Format the output and add 2 to the second value.
   [:                                                Apply the twin prime to the formatter.

Basically, if n is 4, this creates a recursion tree like this:
 let T be the recursion inside t
 and numbers between rows the return values of according function
   (t * n) 3
-> (t * 4) 3
-> t  t  t  t  3
   17 11 5  3
-> (T  T) (T  T) T  T  3
    17 13  11 7  5  3
-> 17

C #, 265

using System.Linq;class P{static void Main(string[] args){var i=int.Parse(args[0]);int f=0,c=0;for(int j=1;;j+=2){var b=(Enumerable.Range(1,j).Count(x=>j%x==0)==2);if(f==0 && b){f=j;continue;}if(b){c++;if(c==i){System.Console.WriteLine(f+","+j);break;}j-=2;}f=0;}}}

Ruby 94

require'mathn'
n=gets.to_i
a=1
(a+=2;a.prime?&&(a+2).prime?&&n-=1)while n>0
$><<"#{a}, #{a+2}"

Tes online: http://ideone.com/B2wxnG

Perl, 100 95

$n=<>;$i=3;while($c<$n&&($l=$i++)){$i++until!grep{$i%$_<1}(2..$i-1);$c++if$i-$l<3}print"$l, $i"

Tidak Disatukan:

$n = <>;          # Read from STDIN
$i = 3;           # Tiny hack because I know I don't need the number 2
while ($c<$n && ($l = $i++)) {   # $c counts the pairs, $l is the last prime
  $i++ until ! grep {$i%$_<1} (2..$i-1);   # Increase $i until it's not divisible by anything
  $c++ if $i-$l < 3   # If $i and $l are twin primes, count it
}
print "$l, $i"    # That damned comma added a whole character to my code!

T-SQL (2008+): 344

Brute paksa sebuah CTE untuk menemukan bilangan prima, fungsi jendela untuk menghitung n, diikuti oleh gabungan untuk menemukan kembarannya. Bekerja dalam hitungan detik untuk keluaran <1.000, tepat di bawah satu menit untuk keluaran <10.000.

Golf (SQLFiddle di sini ):

WITH x(i) AS(SELECT 99 UNION ALL SELECT i-2
FROM x WHERE i>3),z AS(SELECT RANK()OVER(ORDER BY x.i)n,x.i
FROM x x LEFT JOIN x y ON x.i%y.i=0 AND y.i NOT IN(x.i,1)
WHERE y.i IS NULL)SELECT LTRIM(a)+', '+LTRIM(b)FROM(SELECT RANK()
OVER(ORDER BY x.i)n,x.i a,y.i b FROM z x,z y WHERE x.n=y.n-1
AND x.i=y.i-2) o WHERE n=3
OPTION(MAXRECURSION 0)

Terbaca:

WITH x(i) AS (
   SELECT 99
    UNION ALL
   SELECT i-2
   FROM x
   WHERE i > 3
)
,z AS (
SELECT RANK()OVER(ORDER BY x.i)n,x.i
FROM x x
WHERE NOT EXISTS
  (SELECT *
   FROM x y
   WHERE x.i%y.i = 0
    AND y.i NOT IN (x.i,1)
  )
)
SELECT LTRIM(a)+', '+LTRIM(b)
FROM (
    SELECT RANK()OVER(ORDER BY x.i)n,x.i a, y.i b
    FROM z x, z y
    WHERE x.n = y.n+1
    AND x.i = y.i+2
) o
WHERE n = 3
OPTION(MAXRECURSION 0)

GolfScript 46

~[1 3]\{\{))}%.{:x,{)x\%!},,2=}/*@\-.}do;', '*

Tes online: tautan

Kode beranotasi:

~                       # parse the input as an int
[1 3]                   # add the array [1, 3] on the stack
\                       # invert the items on the stack
{                       # begin loop
  \                     # bring the array to the top of the stack
  {))}%                 # add 2 to each of the numbers in the array
  .{:x,{)x\%!},,2=}/    # check if numbers are prime (leaves a 0 or 1 for both numbers on the stack)
  *                     # multiply the two 0/1 numbers (will only get 1 if both are 1)
  @\-                   # subtract the result from the inital int
  .                     # copy the new int value on the stack to be consumed by the 'do' loop
}do                     # repeat until the initial int was taken down to 0
                        # at this point the array contains the two numbers we're looking for
;                       # get rid of the 0 from the stack
', '*                   # format the output

PHP 5.4, 223

Bukan yang lebih kecil, Tapi satu coba dari php.

$n=$argv[1];function i($k){for($i=2;$i<=(int)($k/2);$i++)if($k%$i==0)return 0;return 1;}function t($t){return (i($t) && i($t+2))?1:0;}$g=1;$d=0;do{if(t($g)==1){if($d<$n){$d++;}else{print_r([$g,$g+2]);break;}}$g++;}while(1);

C 309

Terus mendapatkan bilangan prima berikutnya dan menyimpan istilah ganjil dan genap kemudian memeriksa apakah perbedaannya adalah dua.

int main()
{
int n;
scanf("%d",&n);
int a=2,b=3,k=2,q;
int odd=1;
int p;
if(n>0)
{
while(n)
{
k++;
p=1;
q=ceil(sqrt(k));
for(int i=2;i<=q;i++)
{
if(k%i==0)
{
p=0;
break;
}
}
if(p)
{
if(odd%2==0)a=k;
else b=k;
if(abs(a-b)==2)n--;
odd++;
}
}
}
printf("%d %d\n",a,b);
return 0;
}

R, 91 karakter

a=scan();n=1;p=5;while(n!=a){p=p+1;q=p-2;if(sum(!p%%2:p,!q%%2:q)<3)n=n+1};cat(q,p,sep=", ")

Tidak ada yang benar-benar mewah:

a=scan()
n=1
p=5
while(n!=a){
    p=p+1
    q=p-2
    if(sum(!p%%2:p,!q%%2:q)<3) # Check that p and q are both primes by checking
       n=n+1                   # the number of zeroes resulting from 
}                              # p modulo each integers 2 to p and same for q
cat(q,p,sep=", ")

Pemakaian:

> a=scan();n=1;p=5;while(n!=a){p=p+1;q=p-2;if(sum(!p%%2:p,!q%%2:q)<3)n=n+1};cat(q,p,sep=", ")
1: 10
2: 
Read 1 item
107, 109

Japt, 23 19 byte

-4 byte terima kasih kepada Shaggy

@µX°j ©°Xj}f
[UU+2]

Jalankan secara online

JavaScript (Node.js), 162 karakter

Membaca dari stdin, output ke stdout, keluar "awal" untuk input <= 0.

t=process.argv[2],c=0,l=1;if(t>0){for(i=0;;i++){p=!Array(i+1).join(1).match(/^1?$|^(11+?)\1+$/);if(p){if(i-2==l){if(c>=t-1){console.log(l+", "+i);break}c++}l=i}}}

Penggunaan (skrip di atas disimpan sebagai ntp.js):

>for /l %x in (0, 1, 10) do node ntp.js %x
>node ntp.js 0
>node ntp.js 1
3, 5
>node ntp.js 2
5, 7
>node ntp.js 3
11, 13
>node ntp.js 4
17, 19
>node ntp.js 5
29, 31
>node ntp.js 6
41, 43
>node ntp.js 7
59, 61
>node ntp.js 8
71, 73
>node ntp.js 9
101, 103
>node ntp.js 10
107, 109

AWK - 129

File fsoe-pairs.awk:

{n=2;N=1
for(;;){if(n in L){p=L[n];del L[n]}else{p=n
if(n-N==2)if(!--$0){print N", "n;exit}N=n}P=p+n++
while(P in L)P+=p;L[P]=p}}

Menjalankannya:

$ awk -f fsoe-pairs.awk
1
3, 5
$ awk -f fsoe-pairs.awk
2
5, 7
$ awk -f fsoe-pairs.awk
10
107, 109

(Baris 1 setelah perintah dimasukkan, baris 2 adalah output)

Ini didasarkan pada algoritma generator utama sendiri yang saya sebut "saringan mengambang erastosthenes" (sampai saya menemukannya dijelaskan di sini) yang hanya menyimpan bagian yang diperlukan dari saringan dan bilangan prima yang sudah dihitung.

Python 2 (75)

c=input()
n=3
while c:n+=2;c-=all(n%i&~2for i in range(2,n-2))
print(n-2,n)

Jadi apa yang terjadi di sini?

Pertama, mari kita lihat ekspresi all(n%i&~2for i in range(2,n-2)), yang memeriksa apakah(n-2,n) sepasang bilangan prima kembar.

Ekspresi yang lebih sederhana all(n%i for i in range(2,n))hanya memeriksa apakah nprima dengan mencoba setiap pembagi idalam rentang 2<=i<=n-1, dan melihat apakah semua yang tersisa adalah nol. Ini allmemeriksa persis ini, karena Python memperlakukan 0sebagai Falsedan semua nomor lainnya sebagaiTrue .

Sekarang, amati bahwa (n-2)%i==0tepat ketika n%i==2untuk pembagi i>2. Jadi, kita bisa melakukan pemeriksaan awal ndan n-2sekaligus dengan memeriksa sisanya untuk keduanya 0dan 2. Ini bisa dilakukan sebagai all(n%i not in [0,2] for i in range(2,n-2)). Kami hanya mencoba pembagi dalam rentang 2<=i<=n-3demi n-2, tetapi ini sudah cukup untuk nsejak itu n-1dan n-2tidak dapat menjadi pembagi kecuali n<=4. Kami hanya akan mencoba yang aneh nmulai dari 5untuk menghindari komplikasi dan pembagi ini i=2.

Kami memasukkan ekspresi n%i not in [0,2]ke dalam n%i&~2, mengingat itu 0False dan angka lainnya True. Prioritas operator (n%i)&(~2)itulah yang dibutuhkan. Bit-komplemen ~2adalah ...11111101, jadi bitwise-nya anddengan angka nol-keluar 2nilai tempat biner. Ini memberi 0(yaitu, False) hanya untuk 0dan 2, persis apa yang kita inginkan.

Fiuh! Sekarang kita memiliki ekspresi all(n%i&~2for i in range(2,n-2))memeriksa apakah nnomor atas dari pasangan perdana kembar. Yang tersisa adalah beralih pada mereka sampai kita melihat cmereka, di mana cnomor yang dimasukkan. Kami mulai dengan 5dan terus menghitung 2untuk menghindari masalah pembagi. Kami mengurangi csetiap kali kami menemukan nyang berfungsi, berhenti ketika c=0. Akhirnya, kami mencetak pasangan kembar utama yang kami akhiri.

T-SQL (2012 +), 255 karakter

Pencari utama kembar T-SQL yang lebih ringkas yang juga sedikit mempercepat.

with t(n)as(select 2+number from spt_values where type='p')select*from(select concat(b,', ',a),rank()over(order by a)from(select n,lag(n)over(order by n)from t where not exists(select*from t f where f.n<t.n and t.n%f.n=0))z(a,b)where a=b+2)r(s,k)where k=2

Format yang dapat dibaca manusia ::

    with t(n)as(
        select 2+number 
        from spt_values 
        where type='p'
    )
    select *
    from(
        select concat(b,', ',a),rank() over (order by a)
        from(
            select n, lag(n) over(order by n)


    from t 
        where not exists(
            select 1 from t f 
            where f.n<t.n and t.n%f.n=0)
    ) z(a,b)
    where a=b+2
) r(s,k)
where k=2

Inti dasarnya adalah kita menggunakan tabel angka bawaan (master..spt_values ​​type = 'p') dan alias dengan CTE sebagai sesuatu yang pendek. Kami menambahkan 2 untuk menghilangkan kekhawatiran menarik 0 atau 1 kesalahan sepele untuk set kami, jadi sekarang kami memiliki kandidat 2,2050.

Z, kueri paling dalam mendapatkan semua bilangan prima dari 2 hingga 2050, dengan memfilter nomor apa pun yang dapat dibagi dengan angka kurang dari n. Kami kemudian menggunakan fungsi windowing T-SQL 2012 yang bagus lagyang memungkinkan kami menarik hasil sebelumnya, jadi sekarang hasil Z a dan b adalah bilangan prima P[n]dan P[n-1]masing - masing. Kueri R membuat string keluaran, dan memfilter bilangan prima non-kembar dan juga membuat nomor urut untuk keluaran yang kita sebut K. Akhirnya kueri R terakhir memungkinkan kita untuk memfilter dan mendapatkan bilangan kembar Kth dengan mengubah variabelnya.

Mathematica - 71 byte

n=Input[];
i=j=0;
While[j<n,i++;If[And@@PrimeQ[x={i,i+2}],j++]];Print@x