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. 


using System;
 
class Program {
 
    static uint[] res = new uint[10];
    static uint ri = 1, p = 10, count = 0;
 
    static void TabulateTwinPrimes(uint bound) {
        if (bound < 5) return; count++;
        uint cl = (bound - 1) >> 1, i = 1, j,
             limit = (uint)(Math.Sqrt(bound) - 1) >> 1;
        var comp = new bool[cl]; bool lp;
        for (j = 3; j < cl; j += 3) comp[j] = true;
        while (i < limit) {
            if (lp = !comp[i]) {
                uint pr = (i << 1) + 3;
                for (j = (pr * pr - 2) >> 1; j < cl; j += pr)
                    comp[j] = true;
            }
            if (!comp[++i]) {
                uint pr = (i << 1) + 3;
                if (lp) {
                    if (pr > p) {
                        res[ri++] = count;
                        p *= 10;
                    }
                    count++;
                    i++;
                }
                for (j = (pr * pr - 2) >> 1; j < cl; j += pr)
                    comp[j] = true; 
            }
        }
        cl--;
        while (i < cl) {
            lp = !comp[i++];
            if (!comp[i] && lp) {
                if ((i++ << 1) + 3 > p) {
                    res[ri++] = count;
                    p *= 10;
                }
                count++;
            }
        }
        res[ri] = count;
    }
 
    static void Main(string[] args) {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        string fmt = "{0,9:n0} twin primes below {1,-13:n0}";
        TabulateTwinPrimes(1_000_000_000);
        sw.Stop();
        p = 1;
        for (var j = 1; j <= ri; j++)
            Console.WriteLine(fmt, res[j], p *= 10);
        Console.Write("{0} sec", sw.Elapsed.TotalSeconds);
    }
}