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. 


Function IsPrime(x As Long) As Boolean
    Dim i As Long
    If x Mod 2 = 0 Then
        Exit Function
    Else
        For i = 3 To Int(Sqr(x)) Step 2
            If x Mod i = 0 Then Exit Function
        Next i
    End If
    IsPrime = True
End Function
 
Function TwinPrimePairs(max As Long) As Long
    Dim p1 As Boolean, p2 As Boolean, count As Long, i As Long
    p2 = True
    For i = 5 To max Step 2
        p1 = p2
        p2 = IsPrime(i)
        If p1 And p2 Then count = count + 1
    Next i
    TwinPrimePairs = count
End Function
 
Sub Test(x As Long)
    Debug.Print "Twin prime pairs below" + Str(x) + ":" + Str(TwinPrimePairs(x))
End Sub
 
Sub Main()
    Test 10
    Test 100
    Test 1000
    Test 10000
    Test 100000
    Test 1000000
    Test 10000000
End Sub