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. 


primes = [2, 3, 5, 7, 11, 13, 17, 19]
 
 
def count_twin_primes(limit: int) -> int:
    global primes
    if limit > primes[-1]:
        ram_limit = primes[-1] + 90000000 - len(primes)
        reasonable_limit = min(limit, primes[-1] ** 2, ram_limit) - 1
 
        while reasonable_limit < limit:
            ram_limit = primes[-1] + 90000000 - len(primes)
            if ram_limit > primes[-1]:
                reasonable_limit = min(limit, primes[-1] ** 2, ram_limit)
            else:
                reasonable_limit = min(limit, primes[-1] ** 2)
 
            sieve = list({x for prime in primes for x in
                          range(primes[-1] + prime - (primes[-1] % prime), reasonable_limit, prime)})
            primes += [x - 1 for i, x in enumerate(sieve) if i and x - 1 != sieve[i - 1] and x - 1 < limit]
 
    count = len([(x, y) for (x, y) in zip(primes, primes[1:]) if x + 2 == y])
 
    return count
 
 
def test(limit: int):
    count = count_twin_primes(limit)
    print(f"Number of twin prime pairs less than {limit} is {count}\n")
 
 
test(10)
test(100)
test(1000)
test(10000)
test(100000)
test(1000000)
test(10000000)
test(100000000)