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. 


 
load "stdlib.ring"
 
limit = list(7)
for n = 1 to 7
    limit[n] = pow(10,n)
next
 
TwinPrimes = []
 
for n = 1 to limit[7]-2
    bool1 = isprime(n)
    bool2 = isprime(n+2)
    bool = bool1 and bool2
    if bool =1 
       add(TwinPrimes,[n,n+2])
    ok
next
 
numTwin = list(7)
len = len(TwinPrimes)
 
for n = 1 to len
    for p = 1 to 6
        if TwinPrimes[n][2] < pow(10,p) and TwinPrimes[n+1][1] > pow(10,p)-2
           numTwin[p] = n
        ok
    next
next 
 
numTwin[7] = len
 
for n = 1 to 7
    see "Maximum: " + pow(10,n) + nl
    see "twin prime pairs below " + pow(10,n) + ": " + numTwin[n] + nl + nl
next 
 