D. Soldier and Number Game

题意：给出a和b(1 <= b <= a <= 5e6)，问a!/b!变成1，最多要经过多少轮？没轮可以选择一个它的因子来除它。

思路：质因子数量，先线性筛，再质因子分解每个数，再前缀和，然后O1查询。

总结：在模板中使用范围质数筛选时，当范围到了5e6就MLE了，没法弄，最后用的线性筛+质因子分解。考虑要不要为模板中单独加一个统计范围内每个数的质因子数量的函数？

/*
 * PrimeNumberManipulator(质数类)
 * 设计思想：基于面向对象的思想的质数管理类。
 * 基于面向对象的编程思想，本方法尽可能多的隐藏了内部实现的细节，并且将必要的编程接口暴露在外部，并需要对这些接口进行直接的修改。
 *                             注意事项：第一个模板参数的数值必须是int型（在竞赛中范围最大是1e8)
 *                                      第二个模板参数是代表是否对第一个参数的范围内每个数进行质数统计（范围大概是1e6不会TLE）。
 *
 * gitHub(仓库地址): https://github.com/yxc-s/programming-template.git
 */












template<typename T, typename U>
class PrimeNumberManipulator{
public:
	template<typename V = T>
	using EnableIfInt    =   typename std::enable_if<std::is_same<V, int>::value, V>::type;
	using primeType      =   typename std::decay<decltype(T::value)>::type;
	using rangePrimeType =   typename std::decay<decltype(U::value)>::type;

	PrimeNumberManipulator(EnableIfInt<primeType>* = 0, EnableIfInt<rangePrimeType>* = 0 ){
		sievePrimes();
		getRangePrimes();
	}

	const std::vector<int>& getPrimeArray() const {
		return prime_values_;
	}

	const std::vector<std::vector<std::pair<int, int>>>& getRangePrimesArray() const {
		return range_prime_values_;
	}

	/* 获取单个数的质因子及出现次数 */
	template <typename V>
	std::vector<std::pair<V, int>> getUniquePrimes(V x){
		std::vector<std::pair<V, int>> res;
		for (const auto& prime : prime_values_){
			if (1ll * prime * prime > x){
				break;
			}
			int cnt = 0;
			while (x % prime == 0){
				x /= prime;
				cnt ++;
			}
			if (cnt){
				res.emplace_back(prime, cnt);
			}
		}
		if (x > 1){
			res.emplace_back(x, 1);
		}
		return res;
	}

	/* 统计不同的质数个数 */
	template<typename V>
	int countUniquePrimes(V x){
		int ans = 0;
		for (const auto& prime : prime_values_){
			if (prime > x / prime){
				break;
			}
			ans ++;
			while (x % prime == 0){
				x /= prime;
			}
		 }
		return ans + (x > 1);
	}

	/* 统计所有的质数 */
	template<typename V>
	int countAllPrimes(V x){
		int ans = 0;
		for (const auto& prime : prime_values_){
			if (prime > x / prime){
				break;
			}
			while (x % prime == 0){
				x /= prime;
				ans ++;
			}
		}
		return ans + (x > 1);
	}

	/* 判定质数，当筛选范围为1e8时，最多可判断1e16的质数*/
	template<typename V>
	bool isPrime(V x){
		if (x <= getPrimeLimit()){
			return bs_[x];
		}
		for (const auto& prime : prime_values_){
			if (x % prime == 0){
				return false;
			}
		}
		return true;
	}

	/* 统计因子数量 */
	template<typename V>
	int countDivisors(V x){
		int ans = 1;
		for (const auto& prime : prime_values_){
			if (prime > x / prime){
				break;
			}
			int power = 0;
			while (x % prime == 0){
				x /= prime;
				power ++;
			}
			ans *= power + 1;
		}
		return x > 1 ? ans * 2 : ans;
	}


private:
	std::bitset<100000010>                            bs_;
	std::vector<int>                                  prime_values_;
	std::vector<std::vector<std::pair<int, int>>>     range_prime_values_;


private:
	constexpr primeType      getPrimeLimit()      { return T::value; }
	constexpr rangePrimeType getRangePrimeLimit() { return U::value; }
	/* 线性筛 */
	void sievePrimes(){
		bs_.set();
		bs_[0] = bs_[1] = 0;
		for (int i = 2; i <= getPrimeLimit(); ++i){
			if (bs_[i]){
				prime_values_.emplace_back(i);
			}
			for (const auto& prime : prime_values_){
				if (1ll * i * prime > getPrimeLimit()){
					break;
				}
				bs_[i * prime] = 0;
				if (i % prime == 0){
					break;
				}
			}
		}
	}

	/* 获取[1, x]范围内每个数的质因子及其出现次数*/
	void getRangePrimes(){
		range_prime_values_.resize(getRangePrimeLimit() + 1);
		for (int i = 2; i <= getRangePrimeLimit(); ++i){
			if (range_prime_values_[i].empty()){
				for (int j = i; j <= getRangePrimeLimit(); j += i){
					int cnt = 0;
					int num = j; 
					while (num % i == 0){
						cnt ++;
						num /= i;
					}
					range_prime_values_[j].emplace_back(i, cnt);
				}
			}
		}
	}


};


constexpr int N = (int)5e6;
constexpr int  PRIME_VALUE_LIMIT   =   N + 10;              /*最多可以到1e8*/
constexpr int  RANGE_VALUE_LIMIT   =   0;        /*目测最多到1e6*/
using Primer = PrimeNumberManipulator<std::integral_constant<decltype(PRIME_VALUE_LIMIT), PRIME_VALUE_LIMIT>, 
									 std::integral_constant<decltype(PRIME_VALUE_LIMIT), RANGE_VALUE_LIMIT>>;

Primer primer;
const std::vector<int>&                              primes = primer.getPrimeArray();
const std::vector<std::vector<std::pair<int, int>>>& range_primes = primer.getRangePrimesArray();

/*
TODO: 第二个模板参数要不要也换成跟第一个模板参数相同的类型，来单独进行筛选？
	  将大质数的算法也写进去。
	   欧拉函数，莫比乌斯函数。
*/

using namespace std;
array<int, N + 20> pref{};
void preProcess(){
	for (int i = 1; i <= N; ++i){
		pref[i] = pref[i - 1] + primer.countAllPrimes(i);
	}
}




void solve(){
	int a, b;
	cin >> a >> b;
	cout << (pref[a] - pref[b]) << '\n';
}