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 java.math.BigInteger;
import java.util.Scanner;
 
public class twinPrimes {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Search Size: ");
        BigInteger max = input.nextBigInteger();
        int counter = 0;
        for(BigInteger x = new BigInteger("3"); x.compareTo(max) <= 0; x = x.add(BigInteger.ONE)){
            BigInteger sqrtNum = x.sqrt().add(BigInteger.ONE);
            if(x.add(BigInteger.TWO).compareTo(max) <= 0) {
                counter += findPrime(x.add(BigInteger.TWO), x.add(BigInteger.TWO).sqrt().add(BigInteger.ONE)) && findPrime(x, sqrtNum) ? 1 : 0;
            }
        }
        System.out.println(counter + " twin prime pairs.");
    }
    public static boolean findPrime(BigInteger x, BigInteger sqrtNum){
        for(BigInteger divisor = BigInteger.TWO; divisor.compareTo(sqrtNum) <= 0; divisor = divisor.add(BigInteger.ONE)){
            if(x.remainder(divisor).compareTo(BigInteger.ZERO) == 0){
                return false;
            }
        }
        return true;
    }
}
 