# Twins challenge

**Problem statement**

Lia is fascinated by anything she considers to be a twin. She calls a pairs of positive integers, and , twins if:

– They are both prime. A prime number is an integer greater than that has no positive divisors other than and itself.

– Their absolute difference is exactly equal to (i.e., ).

Given an inclusive interval of integers from to , can you help Lia find the number of pairs of twins there are in the interval (i.e., )? Note that pairs and are considered to be the same pair.

**Input Format**

Two space-separated integers describing the respective values of and .

**Constraints**

**Output Format**

Print a single integer denoting the number of pairs of twins.

**Sample Input 0**

3 13

**Sample Output 0**

3

**Explanation 0**

There are three pairs of twins: , and .

**Sample Input Files**

twins-challenge-in1, twins-challenge-out1

twins-challenge-in2, twins-challenge-out2

twins-challenge-in3, twins-challenge-out3

twins-challenge-in4, twins-challenge-out4

twins-challenge-in5, twins-challenge-out5

**Solution**

We will solve this problem by reducing it to two familiar problems. Sieve of Eratosthenes in interval and Find the number of pairs in an array whose difference is k. So we will first store all primes in the interval in a set and then find the number of pairs in the set whose difference is .

The implementation is listed below.

**Full code**

public class Twins { // Sieve of Eratosthenes for [n,m] public static Setprimes(int n, int m) { Set primes = new TreeSet<>(); int k = (int) Math.sqrt(m); boolean[] a = new boolean[k + 1]; boolean[] b = new boolean[m - n + 1]; for (int i = 0; i < a.length; i++) { a[i] = true; } for (int i = 0; i < b.length; i++) { b[i] = true; } for (int i = 2; i <= k; i++) { if (a[i]) { for (int j = i * i; j <= k; j = j + i) { a[j] = false; } for (int j = Math.max(2, (n + i - 1) / i) * i; j <= m; j = j + i) { b[j - n] = false; } } } for (int i = 0; i < b.length; i++) { if (b[i] && (i + n) > 1) { primes.add(i + n); } } return primes; } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); Set primes = primes(n, m); int count = 0; for (int prime : primes) { if (primes.contains(prime + 2)) { count++; } } System.out.println(count); } }