Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Twins challenge

Sharing is caring!

Problem statement
Lia is fascinated by anything she considers to be a twin. She calls a pairs of positive integers, i and j, twins if:
– They are both prime. A prime number is an integer greater than that has no positive divisors other than 1 and itself.
– Their absolute difference is exactly equal to 2 (i.e., |j - i| = 2).

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

Input Format
Two space-separated integers describing the respective values of n and m.

Constraints
1 \le n \le m \le 10^9
m - n \le 10^6

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: (3,5), (5,7) and (11,13).

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 \left[n,m\right] in a set and then find the number of pairs in the set whose difference is 2.

The implementation is listed below.

Full code

public class Twins {
    // Sieve of Eratosthenes for [n,m]
    public static Set primes(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);
    }
}