UVa 11876 - N + NOD (N)

#include <stdio.h>
#include <vector>
#include <utility>
using namespace std;

// Gets the prime factors of a number with the exponents. No need to have the sieve beforehand because it loops odd numbers (not primes).
// e.g. getPrimeFactorizationOf(2) = {(2,2)(3,1)}
vector<pair<int, int> > getPrimeFactorizationOf(int n) {
	vector<pair<int, int> > factors;
	pair<int, int> current_factor = pair<int, int>(2, 0);
	while (n % 2 == 0) {
		current_factor.second++;
		n /= 2;
	}
	if (current_factor.second > 0)
		factors.push_back(current_factor);

	for (int candidate = 3; candidate * candidate <= n && n > 1; candidate += 2) {
		int exponent = 0;
		while (n % candidate == 0) {
			exponent++;
			n /= candidate;
		}
		if (exponent > 0)
			factors.push_back(pair<int, int>(candidate, exponent));
	}
	if (n > 1)
		factors.push_back(pair<int, int>(n, 1));
	return factors;
}

int numberOfDivisorsOf(int n) {
	vector<pair<int, int> > factors = getPrimeFactorizationOf(n);
	int numberOfDivisors = 1;
	for (int i = 0; i < factors.size(); i++)
		numberOfDivisors *= (factors[i].second + 1);
	return numberOfDivisors;
}

vector<int> seq;

void generateSequence() {
	int last_element = 1;
	while (last_element <= 1000000) {
		seq.push_back(last_element);
		last_element = last_element + numberOfDivisorsOf(last_element);
	};
	seq.push_back(last_element);
}

/**
 * Returns the index of value or the index of the successor
 * e.g. bin_search( {10,11,12,14,15}, 11) = 1
 * e.g. bin_search( {10,11,12,14,15}, 13) = 3
 */
int bin_search(int value, const vector<int> & sorted_vector) {
	int left = 0;
	int right = sorted_vector.size() - 1;
	while (left < right) {
		int mid = (left + right) >> 1;
		if (sorted_vector[mid] == value)
			return mid;
		if (sorted_vector[mid] > value)
			right = mid - 1;
		else
			left = mid + 1;
	}
	while (right < sorted_vector.size() && sorted_vector[right] < value)
		right++;
	return right;
}

int main() {
	generateSequence();
	int cases;
	scanf("%d", &cases);
	for (int cas = 1; cas <= cases; cas++) {
		int a, b;
		scanf("%d%d", &a, &b);
		int a_pos = bin_search(a, seq);
		int b_pos = bin_search(b, seq);
		if (b_pos < seq.size() && seq[b_pos] == b)
			b_pos++;
		printf("Case %d: %d\n", cas, b_pos - a_pos);
	}
}