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.*
 
fun main() {
    val input = Scanner(System.`in`)
    println("Search Size: ")
    val max = input.nextBigInteger()
    var counter = 0
    var x = BigInteger("3")
    while (x <= max) {
        val sqrtNum = x.sqrt().add(BigInteger.ONE)
        if (x.add(BigInteger.TWO) <= max) {
            counter += if (findPrime(
                    x.add(BigInteger.TWO),
                    x.add(BigInteger.TWO).sqrt().add(BigInteger.ONE)
                ) && findPrime(x, sqrtNum)
            ) 1 else 0
        }
        x = x.add(BigInteger.ONE)
    }
    println("$counter twin prime pairs.")
}
 
fun findPrime(x: BigInteger, sqrtNum: BigInteger?): Boolean {
    var divisor = BigInteger.TWO
    while (divisor <= sqrtNum) {
        if (x.remainder(divisor).compareTo(BigInteger.ZERO) == 0) {
            return false
        }
        divisor = divisor.add(BigInteger.ONE)
    }
    return true
}