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. 


 
# syntax: GAWK -f TWIN_PRIMES.AWK
BEGIN {
    n = 1
    for (i=1; i<=6; i++) {
      n *= 10
      printf("twin prime pairs < %8s : %d\n",n,count_twin_primes(n))
    }
    exit(0)
}
function count_twin_primes(limit,  count,i,p1,p2,p3) {
    p1 = 0
    p2 = p3 = 1
    for (i=5; i<=limit; i++) {
      p3 = p2
      p2 = p1
      p1 = is_prime(i)
      if (p3 && p1) {
        count++
      }
    }
    return(count)
}
function is_prime(x,  i) {
    if (x <= 1) {
      return(0)
    }
    for (i=2; i<=int(sqrt(x)); i++) {
      if (x % i == 0) {
        return(0)
      }
    }
    return(1)
}
 