| Bytes | Lang | Time | Link |
|---|---|---|---|
| 080 | Raku Perl 6 rakudo | 241213T204226Z | xrs |
| nan | PHP 8.3 145char | 231210T181929Z | Willtech |
| 063 | APLNARS | 231213T062801Z | Rosario |
| 153 | PHP | 231210T120749Z | lukas.j |
| 7125 | Vyxal ṡ | 231206T150829Z | pacman25 |
| 011 | Husk | 210301T031102Z | Razetime |
| 019 | Japt | 190301T213344Z | Oliver |
| 071 | Mathematica | 140620T040617Z | mfvonh |
| 255 | TSQL2012+ | 140619T164455Z | Michael |
| 075 | Python 2 | 140619T003134Z | xnor |
| 087 | Perl | 140616T194819Z | Zaid |
| 265 | C# | 140616T143109Z | Erez Rob |
| 113 | C | 140616T062040Z | millinon |
| 344 | TSQL 2008+ | 140617T173344Z | comforta |
| 129 | AWK | 140617T093403Z | user1921 |
| 162 | JavaScript Node.js | 140617T134139Z | zamnuts |
| 051 | J | 140616T163445Z | seequ |
| 091 | R | 140617T084208Z | plannapu |
| nan | 140616T091705Z | edc65 | |
| 026 | CJam | 140616T054510Z | Dennis |
| 063 | Mathematica | 140616T170300Z | Szabolcs |
| 309 | C | 140616T192858Z | bacchusb |
| 223 | PHP 5.4 | 140616T133747Z | kuldeep. |
| 095 | Perl | 140616T061137Z | Tal |
| 118 | Haskell | 140616T060836Z | johnchen |
| 046 | GolfScript | 140616T193124Z | Cristian |
| 094 | Ruby | 140616T154723Z | Cristian |
| 026 | CJam | 140616T134853Z | aditsu q |
Raku (Perl 6) (rakudo), 80 bytes
say ((^Inf).grep(*.is-prime).rotor(2=>-1).grep({.[1]-.[0]==2}))[$N-1].join(', ')
PHP 8.3 145char
Runs up to 10,000 actually I had difficulty with readline simulating stdin not using this very often.
Programming support: Notepad
$j=readline();for($i=1;$i<10000;$i=$i+2){if((gmp_prob_prime($i))&&(gmp_prob_prime($i+2))){$x++;}if($x==$j){break;}}echo"$i, "; $i=$i+2;echo"$i";
$j=readline();
for ($i=1;$i<10000;$i=$i+2) {
if ((gmp_prob_prime($i))&&(gmp_prob_prime($i+2))) {$x++;}
if($x==$j) {break;}
}
echo"$i, ";
$i=$i+2;
echo"$i";
Output $j=[1-12]:
3, 5
5, 7
11, 13
17, 19
29, 31
41, 43
59, 61
71, 73
101, 103
107, 109
137, 139
149, 151
APL(NARS), 63 chars
P;w;p;r
w←⎕⋄p←2
→3×⍳0≥w⋄w-←2=p-⍨r←1πp⋄p←r⋄→2
⎕←∊⍕¨3⌽', ',p,p-2
7+7+28+17+4=63 test
P
⎕:
1
3, 5
P
⎕:
1000
79559, 79561
P
⎕:
100000
18409199, 18409201
PHP (153)
$nth=readline();$i=1;$l=1;$c=0;while(1){$q=0;for($j=1;$j<=$i;$j++){$q+=$i%$j==0?1:0;}if($q==2){if($i-$l==2&&++$c==$nth){echo"$l, $i";break;}$l=$i;}++$I;}
Readable format with properly named variables:
$nth = readline();
$i = 1;
$lastFoundPrime = 1;
$countOfFoundPrimes = 0;
while (1) {
$quotient = 0;
for ($j = 1; $j <= $i; $j++) {
$quotient += $i % $j == 0 ? 1 : 0;
}
if ($quotient == 2) {
if ($i - $lastFoundPrime == 2 && ++$countOfFoundPrimes == $nth) {
echo "$lastFoundPrime, $i";
break;
}
$lastFoundPrime = $i;
}
++$i;
}
And wrapped in a for loop:
foreach (range(1, 10) as $nth) {
$i = 1;
$lastFoundPrime = 1;
$countOfFoundPrimes = 0;
while (1) {
$quotient = 0;
for ($j = 1; $j <= $i; $j++) {
$quotient += $i % $j == 0 ? 1 : 0;
}
if ($quotient == 2) {
if ($i - $lastFoundPrime == 2 && ++$countOfFoundPrimes == $nth) {
echo "$lastFoundPrime, $i";
break;
}
$lastFoundPrime = $i;
}
++$i;
}
echo "\n";
}
Output:
3, 5
5, 7
11, 13
17, 19
29, 31
41, 43
59, 61
71, 73
101, 103
107, 109
Vyxal ṡ, 57 bitsv2, 8.125 7.125 bytes
Þp'⇧æ;i:⇧
Bitstring:
001010110100000101111000110100001000110100111000111011110
0-indexed
Husk, 11 bytes
!fo=2F≠Ẋeİp
non-competing, since it takes input from arguments rather than STDIN.
Returns a 2-element list.
Interesting version using Ψ: Try it online!
Mathematica -- 71 bytes
n=Input[];
i=j=0;
While[j<n,i++;If[And@@PrimeQ[x={i,i+2}],j++]];Print@x
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.
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.
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.
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;}}}
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.
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)
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.
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
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
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
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)
CJam, 29 26 bytes
Y4]{{:)_{mp}/&!}g}q~*", "*
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. ";
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]
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;
}
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);
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!
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.
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
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
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