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. 


#include <cstdint>
#include <iostream>
#include <string>
#include <primesieve.hpp>
 
void print_twin_prime_count(long long limit) {
    std::cout << "Number of twin prime pairs less than " << limit
        << " is " << (limit > 0 ? primesieve::count_twins(0, limit - 1) : 0) << '\n';
}
 
int main(int argc, char** argv) {
    std::cout.imbue(std::locale(""));
    if (argc > 1) {
        // print number of twin prime pairs less than limits specified
        // on the command line
        for (int i = 1; i < argc; ++i) {
            try {
                print_twin_prime_count(std::stoll(argv[i]));
            } catch (const std::exception& ex) {
                std::cerr << "Cannot parse limit from '" << argv[i] << "'\n";
            }
        }
    } else {
        // if no limit was specified then show the number of twin prime
        // pairs less than powers of 10 up to 100 billion
        uint64_t limit = 10;
        for (int power = 1; power < 12; ++power, limit *= 10)
            print_twin_prime_count(limit);
    }
    return 0;
}