Dwie liczby pierwsze są definiowane jako liczby pierwsze bliźniacze, jeśli różnią się o dwa. Na przykład 3 i 5 są liczbami podwójnymi, podobnie jak 29 i 31.

Napisz program, który znajdzie n-tą parę podwójnych liczb pierwszych (gdzie n pochodzi od STDIN) i wydrukuje je na STDOUT, oddzielone przecinkiem i spacją. To jest golf golfowy, więc wygrywa najkrótszy kod.

Przykładowe dane wejściowe:

3

Przykładowe dane wyjściowe:

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-force wszystkie bliźniacze liczby pierwsze i drukuje n- ^tą parę.

CJam, 29 26 bajtów

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

Wypróbuj online.

Przykłady

$ 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

Jak to działa

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 znaków, w oparciu o komentarz ascheplera

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

101 znaków, wcześniejsza odpowiedź

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

Stosowanie:

$ perl ./twin_primes.pl 10
107, 109

Wyjaśnienie

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

Działanie wyrażenia regularnego innego niż pierwotne wyjaśniono w tym pytaniu SO .

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

Przykładowy przebieg:

$ 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

Dzięki za pomoc Dennisa, Bebe i Alchymist.

CJam - 26

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

Działa dla liczb pierwszych mniejszych niż 10000; możesz zastąpić 4wyższym wykładnikiem dla większych liczb (potencjalnie do 10 ²⁰ ), ale program będzie działał wolniej i zużyje więcej pamięci.

Wypróbuj na http://cjam.aditsu.net/

Wyjaśnienie:

1e4,tworzy tablicę [0 1 2 ... 9999]
{mp},wybiera tylko liczby pierwsze
_2f-kopiuje tablicę i odejmuje 2 od każdego elementu
&przecina dwie tablice, w ten sposób znajdując niższe liczby pierwsze z każdej pary podwójnych liczb pierwszych
qiodczytuje dane wejściowe i konwertuje na liczbę całkowitą
(=dostosowuje indeksuje i pobiera odpowiadającą (niższą) liczbę pierwszą z tablicy
_2+kopiuje liczbę pierwszą i dodaje 2
", "\wstawia przecinek i spację między dwiema liczbami pierwszych

Mathematica - 63 znaki

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

Uwagi

Jest to w rzeczywistości dość prosta implementacja. Skrócenie spowodowało prawie brak zaciemnienia.

NextPrime jest wbudowanym, który znajduje następną liczbę pierwszą po liczbie.

NestWhile[NextPrime,#,#2-#1!=2&,2]& to anonimowa funkcja, która znajduje większą liczbę pierwszą następnej pary liczb pierwszych po liczbie.

Neststosuje tę anonimową funkcję nrazy.

Print[#-2,", ",#]&to anonimowa funkcja, która drukuje na standardowe wyjście zgodnie ze specyfikacjami. Niestety samo to zajmuje 18 znaków z 63-znakowego rozwiązania.

Przykład

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

Aktualizacja: Dwa znaki mogą zostać zapisane poprzez ponowne wdrożenie tego rozwiązania CJam . Jednak ten algorytm ogranicza maksymalną wartość n. Po prostu zamień Nest...część naIntersection[#,#-2][[5]]&@Prime@Range[999]

JavaScript (E6) 92 96

Krótszy i zgodny - użyj powłoki spidermonkey do odczytu standardowego wejścia / standardowego zapisu (przecinkiem i spacją). Znajduje 10000. parę 1260989, 1260991 w niecałą minutę na moim komputerze
Może być krótszy przy użyciu p[n]=o=nzamiast p.push(o=n), tak że tablica p jest rzadka. Ale to jest wolniejsze i i tak nie zamierzam wygrywać w kwestii długości kodu.

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)

Aby spróbować w konsoli 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)

Nie golfił

Funkcja, która znalazła wszystkie pierwsze m bliźniaków (zwraca największą wartość):

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
}

Przykład: 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]

Tylko ostatni:

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
}

Następnie weź te 2 linie i dodaj 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 bajtów

Zdecydowałem się na proste podejście. Funkcja tznajduje następną podwójną liczbę pierwszą, podając jako liczbę pierwszą liczbę pierwszą (teraz jest to uwzględnione w ffunkcji). Funkcja fznajduje n-tą podwójną liczbę pierwszą. To też jest pierwszy rzeczywisty program, który napisałem w J.

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

Przykłady:

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

Tylko dla niektórych brwi, miej wersję bez golfa.

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

Wyjaśnienie:

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

Test 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"

Nie golfowany:

$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 force CTE, aby znaleźć liczby pierwsze, funkcja okna, by policzyć n, a następnie łączyć, aby znaleźć bliźniaka. Działa w ciągu sekundy dla wyjść <1000, nieco poniżej minuty dla wyjść <10 000.

Gra w golfa ( tutaj SQLFiddle ):

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)

Czytelny:

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;', '*

Test online: link

Kod z adnotacjami:

~                       # 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

Nie mniejszy, ale jeden z 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

Przechowuje kolejne liczby pierwsze i zapisuje nieparzyste, a nawet terminy, a następnie sprawdza, czy różnica wynosi dwa.

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 znaków

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=", ")

Nic szczególnego:

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=", ")

Stosowanie:

> 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 bajtów

-4 bajty dzięki Shaggy

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

Uruchom to online

JavaScript (Node.js), 162 znaków

Odczytuje ze standardowego wejścia, wyjścia na standardowe wyjście, wychodzi „wcześnie” na wejście <= 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}}}

Użycie (powyższy skrypt zapisany jako 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

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

Uruchamianie:

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

(Pierwszy wiersz po wprowadzeniu polecenia, drugi jest wyprowadzany)

Opiera się to na własnym algorytmie generatora liczb pierwszych, który nazywam „pływającym sitem erastostenów” (dopóki nie znajdę go opisanego gdzie indziej), który przechowuje tylko potrzebną część sita i już obliczone liczby pierwsze.

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)

Co tu się dzieje?

Najpierw spójrzmy na wyrażenie all(n%i&~2for i in range(2,n-2)), które sprawdza, czy (n-2,n)są parą bliźniaczych liczb pierwszych.

Prostsze wyrażenie all(n%i for i in range(2,n))po prostu sprawdza, czy njest liczbą pierwszą, wypróbowując każdy dzielnik iw zakresie 2<=i<=n-1i sprawdzając, czy wszystkie pozostałe są niezerowe. To allsprawdza dokładnie to, ponieważ Python traktuje 0jak Falsei wszystkie inne liczby jako True.

Teraz obserwuj to (n-2)%i==0dokładnie w przypadku n%i==2dzielników i>2. Tak więc, możemy przeprowadzić kontrolę na pierwszości ni n-2jednocześnie sprawdzając pozostałości zarówno dla 0i 2. Można to zrobić jako all(n%i not in [0,2] for i in range(2,n-2)). Próbujemy dzielników w zakresie 2<=i<=n-3tylko ze względu na n-2, ale to wystarcza nrównież od tego czasu n-1i n-2nie możemy być dzielnikami, chyba że n<=4. Spróbujemy tylko nod nieparzystej, 5aby uniknąć tej komplikacji i dzielnika i=2.

My golf wyrażenie n%i not in [0,2]do n%i&~2pamiętając, że 0jest fałszywa i inne numery są True. Priorytet operatora (n%i)&(~2)jest dokładnie tym, czego potrzeba. Uzupełnianie bitów ~2jest ...11111101więc bitowe andz liczbą zerującą 2wartość binarną miejsca. To daje 0(tj. False) Tylko 0i 2dokładnie to, czego chcemy.

Uff! Teraz mamy, że wyrażenie all(n%i&~2for i in range(2,n-2))sprawdza, czy njest najwyższą liczbą bliźniaczych liczb pierwszych. Pozostaje iterować nad nimi, dopóki ich nie zobaczymy c, gdzie cjest wprowadzona liczba. Zaczynamy od 5i odliczamy, 2aby uniknąć problemów z dzielnikami. Zmniejszamy się za ckażdym razem, gdy napotykamy coś, nco działa, zatrzymując się, kiedy c=0. Na koniec drukujemy podwójną parę pierwszą, którą kończymy.

T-SQL (2012 +), 255 znaków

Bardziej kompaktowa wyszukiwarka podwójnych liczb pierwszych T-SQL, która również trochę przyspiesza.

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 czytelny dla człowieka:

    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

Podstawowa zasada polega na tym, że używamy wbudowanej tabeli liczb (master..spt_values ​​type = 'p') i aliasu tego z CTE jako czegoś krótkiego. Dodajemy 2, aby wyeliminować problem ciągnięcia 0 lub 1 trywialnych błędów dla naszego zestawu, więc teraz mamy kandydatów na 2,2050.

Z najbardziej wewnętrzne zapytanie otrzymuje wszystkie liczby pierwsze od 2 do 2050, odfiltrowując dowolną liczbę n, która jest podzielna przez liczbę mniejszą niż n. Następnie używamy fajną T-SQL 2012 okienkowy funkcję lag, która pozwala nam wyciągnąć poprzedni wynik, więc teraz wyniki oo za aib są liczbami pierwszymi P[n]i P[n-1]odpowiednio. Zapytanie R tworzy ciąg wyjściowy i odfiltrowuje niepodzielne liczby pierwsze, a także tworzy numer sekwencyjny dla wyniku, który nazywamy K. Wreszcie ostatnie zapytanie R pozwala nam filtrować i uzyskać Kth liczbę pierwszą przez zmianę jego zmiennej.

Mathematica - 71 bajtów

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