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. 


import math, strformat, strutils
 
const N = 1_000_000_000
 
proc sieve(n: Positive): seq[bool] =
  ## Build and fill a sieve of Erathosthenes.
  result.setLen(n + 1)  # Default to false which means prime.
  result[0] = true
  result[1] = true
  for n in countup(3, sqrt(N.toFloat).int, 2):
    if not result[n]:
      for k in countup(n * n, N, 2 * n):
        result[k] = true
 
let composite = sieve(N)
 
proc findTwins(composite: openArray[bool]) =
  var
    lim = 10
    count = 1     # Start with 3, 5 which is a special case.
    n = 7         # First prime congruent to 1 modulo 3.
  while true:
    if not composite[n] and not composite[n - 2]: inc count
    inc n, 6      # Next odd number congruent to 1 modulo 3.
    if n > lim:
      echo &"There are {insertSep($count)} pairs of twin primes under {insertSep($lim)}."
      lim *= 10
      if lim > N: break
 
composite.findTwins()