Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Two prime numbers are defined as twin primes if they differ by two. For example, 3 and 5 are twin primes as are 29 and 31.

Write a program that finds the nth pair of twin primes (where n comes from STDIN) and prints them on STDOUT, separated by a comma and a space. This is code-golf, so the shortest code wins.

Sample input:

3

Sample output:

11, 13
share|improve this question
5  
Wait... so the user will input the nth pair of twin primes, and you want us to output it? So, just echo back what the user inputs? ;-) –  Iszi Jun 16 at 8:29
    
Hmm... That wording was a bit awkward! :P –  Jwosty Jun 16 at 16:30
add comment

21 Answers 21

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 all twin primes and prints the nth pair.

share|improve this answer
4  
Nice one! By seperating out the filtering function and using interact instead of putStrLn you can go even further and bring this down to 105: a#b=all((>0).rem a)[2..a-b];main=interact$(!!)[show n++", "++show(n+2)|n<-[2..],n#1,(n+2)#2].(+)(-1).read –  Flonk Jun 16 at 14:42
add comment

CJam, 29 26 bytes

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

Try it online.

Examples

$ 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

How it works

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.                                       ";
share|improve this answer
add comment

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

Sample run:

$ 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

Thanks for help from Dennis, bebe, and Alchymist.

share|improve this answer
    
You can save a few bytes by using scanf instead of command line arguments. Also, o=0 is unnecessary, since o is global. –  Dennis Jun 16 at 6:47
    
Thanks, Dennis! –  millinon Jun 16 at 7:23
    
main could hold a default int variable, incrementing c and i in between assignments and statements could shorten the code, the assignment of l could be taken back to the first for loop's third block so you would not need braces and using only one character of separator in printf could definitely make it more compact. –  bebe Jun 16 at 9:51
    
Thanks, bebe! I noticed that I also had c<=i-1, which is just silly. –  millinon Jun 16 at 17:47
    
I don't see a way to shave a byte by incrementing i in the l assignment expression, since the (new) value of i is used to decrement n. Any tips? –  millinon Jun 16 at 22:45
show 1 more comment

Perl, 101 87

87 characters, building over aschepler's comment

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

101 characters, earlier answer

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

Usage:

$ perl ./twin_primes.pl 10
107, 109

Explanation

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

The workings of the non-primality regex is explained in this SO question.

share|improve this answer
    
..what is this? –  TheRare Jun 16 at 19:50
    
@TheRare : It utilizes a regex to check for the primeness of a number. –  Zaid Jun 16 at 19:52
1  
You just blew my mind. Have a +1. –  TheRare Jun 16 at 19:54
    
@TheRare : I added an explanation for why this works. I'm sure there is still room for improvement :) –  Zaid Jun 16 at 20:05
2  
Pretty much what I would have done. Have a few shaved characters: $n=pop;$r='^1$|^(11+?)\1+$';($t=1x$s)=~$r||"11$t"=~$r||--$n||exit say("$s, ",$s+2)while++$s –  aschepler Jun 17 at 0:18
show 1 more comment

CJam - 26

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

It works for primes smaller than 10000; you can replace 4 with a higher exponent for larger numbers (potentially up to 1020), but the program will get slower and will use more memory.

Try it at http://cjam.aditsu.net/

Explanation:

1e4, creates the array [0 1 2 ... 9999]
{mp}, selects only the prime numbers
_2f- copies the array and subtracts 2 from each item
& intersects the two arrays, thus finding the lower primes from each twin prime pair
qi reads the input and converts to integer
(= adjusts the index and gets the corresponding (lower) twin prime from the array
_2+ copies the prime and adds 2
", "\ puts the comma and space between the two primes

share|improve this answer
add comment

Mathematica - 63 characters

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

Notes

This is in fact a rather straightforward implementation. Shortening resulted in almost no obfuscation.

NextPrime is a builtin that finds the next prime after a number.

NestWhile[NextPrime,#,#2-#1!=2&,2]& is an anonymous function that finds the larger prime of the next twin prime pair after a number.

Nest applies this anonymous function n times.

Print[#-2,", ",#]& is an anonymous function that prints to stdout according to the specifications. Sadly this alone takes up 18 characters of the 63 character solution.

Example

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

Update: Two characters could be saved by reimplementing this CJam solution. However, this algorithm limits the maximum value of n. Just replace the Nest... part by Intersection[#,#-2][[5]]&@Prime@Range[999]

share|improve this answer
    
Where's your STDIN? :) –  mfvonh Jun 20 at 4:07
add comment

Javascript (E6) 92 96

Shorter and compliant - use spidermonkey shell to read stdin/write stdout (with comma and space). It finds the 10000th pair 1260989, 1260991 in under a minute on my PC
Could be shorter using p[n]=o=n instead of p.push(o=n), so that the p array is sparse. But that's quite slower, and I'm not going to win for code length anyway.

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)

To try in firefox console:

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)

Ungolfed

A function that found all first m twins (returns the largest value):

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
}

Example: 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]

Just the last:

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
}

Then, take that 2 lines and add 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)
share|improve this answer
add comment

J - 49 60 55 51 bytes

I decided to go with a simple approach. Function t finds the next twin prime given a prime number as input (now this is included in the f function). Function f finds the nth twin prime. This also happens to be the first actual program I've written in J.

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

Examples:

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

Just for some eyebrowraises, have the ungolfed version.

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

Explanation:

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
share|improve this answer
    
This needs a bit more work to conform to the specifications: "prints them on STDOUT, separated by a comma and a space". Of course that's irrelevant to the algorithm, but it does increase the length of the program. –  Szabolcs Jun 16 at 17:05
    
@Szabolcs better? –  TheRare Jun 16 at 17:15
    
Sure, +1. J is pretty cool. –  Szabolcs Jun 16 at 17:17
    
@Szabolcs It really is. Although it reeeeeally bends my mind. Getting easier all the time though (this was the first program I wrote by hand). Also, thanks. –  TheRare Jun 16 at 17:18
add comment

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;}}}
share|improve this answer
2  
+1 but you need to add one space after the comma when you print the mnumbers –  w0lf Jun 16 at 15:38
1  
you can save two more chars: .Count(x=>j%x==0)==2) --> .Count(x=>j%x<1)<3) –  w0lf Jun 16 at 18:35
2  
also, your class could be called P instead of Program and the parameter a instead of args. –  w0lf Jun 16 at 19:32
    
Thanks guys, changed it. –  Erez Robinson Jun 17 at 10:16
1  
Won't compile as it is - you have an extra ) after the .Count(...)<3. You can also save a bit by changing var i=int.Parse(args[0]);int f=0,c=0; to int i=int.Parse(args[0]),f=0,c=0;. You can further save some by extracting the initialiser from the loop, so c=0;for(int j=1; => c=0,j=1;for(;. –  Bob Jun 18 at 0:22
show 2 more comments

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

Online test: http://ideone.com/B2wxnG

share|improve this answer
add comment

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"

Ungolfed:

$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!
share|improve this answer
add comment

T-SQL (2008+): 344

Brute force a CTE to find primes, window function to count n, followed by a join to find the twin. Works in a second for outputs < 1,000, just under a minute for outputs < 10,000.

Golfed (SQLFiddle here):

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)

Legible:

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)
share|improve this answer
add comment

GolfScript 46

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

Online test: link

Annotated code:

~                       # 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
share|improve this answer
add comment

PHP 5.4, 223

Not a smaller one, But one try from 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);
share|improve this answer
add comment

C 309

Keeps getting next primes and store odd and even terms then checks if the difference is two.

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;
}
share|improve this answer
1  
Please not the square root! for (int i=2;i*i<=k;i++) –  edc65 Jun 16 at 20:01
add comment

R, 91 chars

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

Nothing really fancy:

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

Usage:

> 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
share|improve this answer
add comment

JavaScript (Node.js), 162 chars

Reads from stdin, outputs to stdout, exits "early" for 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}}}

Usage (script above saved as 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
share|improve this answer
add comment

AWK - 129

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

Running it:

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

(1st line after command is input, the 2nd one is output)

This is based on an own prime generator algorithm I call "floating sieve of erastosthenes" (until I find it described elswhere) which only stores the needed part of the sieve and the already calculated primes.

share|improve this answer
add comment

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)

So what's going on here?

First, let's look at the expression all(n%i&~2for i in range(2,n-2)), which checks if (n-2,n) are a pair of twin primes.

The simpler expression all(n%i for i in range(2,n)) simply checks if n is prime by trying every divisor i in the range 2<=i<=n-1, and seeing if all remainders are nonzero. This all checks exactly this, since Python treats 0 as False and all other numbers as True.

Now, observe that (n-2)%i==0 exactly when n%i==2 for divisors i>2. So, we can perform the primality check on n and n-2 at the same time by checking the remainders for both 0 and 2. This could be done as all(n%i not in [0,2] for i in range(2,n-2)). We only try divisors in the range 2<=i<=n-3 for the sake of n-2, but this suffices for n as well since n-1 and n-2 can't be divisors unless n<=4. We will only try odd n starting from 5 to avoid this complication and that of the divisor i=2.

We golf the expression n%i not in [0,2] into n%i&~2, remembering that 0 is False and other numbers are True. The operator precedence (n%i)&(~2) is exactly what's needed. The bit-complement ~2 is ...11111101, so its bitwise and with a number zeroes-out the 2's binary place value. This gives 0 (i.e., False) only for 0 and 2, exactly what we want.

Phew! Now we have that the expression all(n%i&~2for i in range(2,n-2)) checks whether n is the upper number of a twin prime pair. What remains is to iterate over them until we see c of them, where c is the inputted number. We start with 5 and counting up by 2 to avoid divisor issues. We decrement c each time we encounter an n that works, stopping when c=0. Finally, we print the twin prime pair that we end with.

share|improve this answer
add comment

T-SQL(2012+),255 characters

A more compact T-SQL twin prime finder that also gets a little bit of a speed up.

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

Human readable format::

    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

The basic gist is we use the built in table of numbers (master..spt_values type='p') and alias that with a CTE as something short. We add 2 to remove the worry of pulling 0 or 1 trivial errors for our set, so now we have candidates of 2,2050.

Z the inner most query gets all primes from 2 to 2050, by filtering out any number n that is divisible by a number less than n. We then use a nifty T-SQL 2012 windowing function lag that lets us pull the previous result, so now Z's results a and b are the primes P[n] and P[n-1] respectively. The R query creates the output string, and filters out non-twin primes and also creates a sequence number for the output we call K. Finally the last query R allows us to filter and get the Kth twin prime by changing its variable.

share|improve this answer
add comment

Mathematica -- 71 bytes

n=Input[];
i=j=0;
While[j<n,i++;If[And@@PrimeQ[x={i,i+2}],j++]];Print@x
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.