Problem of The Day 15 December 2016 — Twins

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

• They are both prime. A prime number is an integer greater than 1 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., [n,m])? 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 < n ≤ m ≤ 109

m — n ≤ 106

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).

Solution will be posted tomorrow.

SOLUTION

The simplest (but too slow) approach will be the following: iterate through integers from N to M and do the prime test for each of them.
The prime test for X will be just iterating through integers from 1 to X and check whether X is divisible by any of them.

The first speed-up: it’s not hard to see that it’s enough to iterate only from 1 to sqrt(X) because if X is not a prime there is at least one prime divisor less than square root of X. But it’s still too slow.

The second speed-up: now we can notice that there is no sense to iterate only through prime integers from 1 to sqrt(N).
So we can precompute with the previous test all the prime numbers less than sqrt(109) and then use only them when we check numbers from N to M.
This should be fast enough to get AC. See the code for details.

CODE

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert> 
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int lst = -1;
    int ans = 0;
    vector primes;
    //checking all primes till 10^9
    for (int i = 2; i*i <= 1E9; i++) {
        bool ok = true;
        for (int j = 2; j*j <= i; j++) { 
            if (i % j == 0) { 
               ok = false; 
               break; 
            } 
        } 
        if (ok && i > 1) {
            primes.push_back(i);
        }
    }
    // starting from N to M and checking through all the number stored in vector Primes
    for (int i = n; i <= m; i++) {
        bool ok = true;
        for (int j = 0; j < primes.size() && primes[j]*primes[j] <= i; j++) { 
            if (i % primes[j] == 0) { 
               ok = false; break; 
            } 
         } 
         if (ok && i > 1) {
            ans += (lst == i - 2);
            lst = i;
        }
    }
    cout << ans << endl;
    return 0;
}