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 <stdbool.h>
#include <stdint.h>
#include <stdio.h>
 
bool isPrime(int64_t n) {
    int64_t i;
 
    if (n < 2)       return false;
    if (n % 2 == 0)  return n == 2;
    if (n % 3 == 0)  return n == 3;
    if (n % 5 == 0)  return n == 5;
    if (n % 7 == 0)  return n == 7;
    if (n % 11 == 0) return n == 11;
    if (n % 13 == 0) return n == 13;
    if (n % 17 == 0) return n == 17;
    if (n % 19 == 0) return n == 19;
 
    for (i = 23; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
 
    return true;
}
 
int countTwinPrimes(int limit) {
    int count = 0;
 
    //       2          3          4
    int64_t p3 = true, p2 = true, p1 = false;
    int64_t i;
 
    for (i = 5; i <= limit; i++) {
        p3 = p2;
        p2 = p1;
        p1 = isPrime(i);
        if (p3 && p1) {
            count++;
        }
    }
    return count;
}
 
void test(int limit) {
    int count = countTwinPrimes(limit);
    printf("Number of twin prime pairs less than %d is %d\n", limit, count);
}
 
int main() {
    test(10);
    test(100);
    test(1000);
    test(10000);
    test(100000);
    test(1000000);
    test(10000000);
    test(100000000);
    return 0;
}