Twin primes are pairs of natural numbers   (P1  and  P2)   that satisfy the following:

     P1   and   P2   are primes
     P1  +  2   =   P2


Task

Write a program that displays the number of pairs of twin primes that can be found under a user-specified number

(P1 < user-specified number & P2 < user-specified number).



Extension

 Find all twin prime pairs under 100000, 10000000 and 1000000000.
 What is the time complexity of the program? Are there ways to reduce computation time?


Examples

> Search Size: 100
> 8 twin prime pairs.

> Search Size: 1000
> 35 twin prime pairs.



Also see

   The OEIS entry: A001097: Twin primes. 
   The OEIS entry: A167874: The number of distinct primes < 10^n which are members of twin-prime pairs. 
   The OEIS entry: A077800: List of twin primes {p, p+2}, with repetition. 
   The OEIS entry: A007508: Number of twin prime pairs below 10^n. 


func IsPrime(N);        \Return 'true' if N is prime
int  N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
    [if rem(N/I) = 0 then return false;
    I:= I+1;
    ];
return true;
];
 
func Twins(Limit);
int  Limit, C, N;
[C:= 0;  N:= 3;
repeat  if IsPrime(N) then
           loop [N:= N+2;
                if N >= Limit then return C;
                if not IsPrime(N) then quit;
                C:= C+1;
                ];
        N:= N+2;
until   N >= Limit;
return C;
];
 
[IntOut(0, Twins(100_000));  CrLf(0);
 IntOut(0, Twins(10_000_000));  CrLf(0);
 IntOut(0, Twins(100_000_000));  CrLf(0);
]