#include <cmath>
#include <vector>
#include <iostream>
#include <tuple>
#include <chrono>

using namespace std;

vector<int> primes({ 2, 3, 5, 7, 11, 13 });

void genPrimes(int max) {
    for (int n = 15; n <= max; n += 2) {
        auto it = primes.begin() + 1;
        for (;;) {
            if (it == primes.end()) {
                primes.push_back(n);
                break;
            }
            if (n % *it == 0) break;
            ++it;
        }
    }
}

int s(int n);

int main() {
    auto t1 = chrono::high_resolution_clock::now();
    constexpr int m = 2300000;
    constexpr int n = 2400000;
    genPrimes(static_cast<int>(sqrt(n)));
    int64_t result = 0;
    for (auto i = m; i <= n; ++i)
    {
        result += s(i);
    }
    cout << result << endl;
    auto t2 = chrono::high_resolution_clock::now();
    cout << "time: " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << "ms" << endl;
}

vector<tuple<int, int>> factorize(int n);
int factorial_power(int m, int p);

int s(int n)
{
    auto factors = factorize(n);
    int lb = 1;
    for (auto v: factors)
    {
        int p;
        int count;
        tie(p, count) = v;
        int lb_value = factorial_power(lb, p);
        if (lb_value >= count) continue;
        int ub = p * count;
        if (count < p)
        {
            lb = ub;
            continue;
        }
        while (lb < ub)
        {
            int median = lb + (ub - lb) / 2;
            int m_value = factorial_power(median, p);
            if (m_value < count)
            {
                lb = median + 1;
            }
            else
            {
                ub = median;
            }
        }
    }
    return lb;
}

int factorial_power(int m, int p)
{
    int result = 0;
    while (m >= p)
    {
        result += m / p;
        m /= p;
    }
    return result;
}

vector<tuple<int, int>> factorize(int n) {
    vector<tuple<int, int>> result;
    for (auto p : primes) {
        int count = 0;
        while (n % p == 0)
        {
            ++count;
            n /= p;
        }
        if (count > 0)
        {
            result.push_back(make_tuple(p, count));
        }
        if (p > n) break;
    }
    if (n > 1)
    {
        result.push_back(make_tuple(n, 1));
    }
    return result;
}

#include <cmath>
#include <vector>
#include <iostream>
#include <tuple>
#include <chrono>
#include <unordered_map>
#include <unordered_set>
#include <list>

using namespace std;

vector<int> primes({ 2, 3, 5, 7, 11 });

int solve(int minA, int maxA, int minB, int maxB);

int main() {
    auto t1 = chrono::high_resolution_clock::now();
    cout << solve(3, 134, 3, 135) << endl;
    auto t2 = chrono::high_resolution_clock::now();
    cout << "time: " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << "ms" << endl;
}

using factors = vector<tuple<int, int>>;
factors factorize(int n);
int h(factors const& v);
int gcd(int a, int b);

int solve(int minA, int maxA, int minB, int maxB)
{
    unordered_map<int, list<factors>> m;
    for (int a = minA; a <= maxA; ++a)
    {
        auto f = factorize(a);
        auto t = h(f);
        auto it = m.find(t);
        if (it == m.end())
        {
            list<factors> v;
            v.emplace_back(move(f));
            m.emplace(t, move(v));
        }
        else
        {
            it->second.emplace_back(move(f));
        }
    }
    int result = 0;
    for (auto t : m)
    {
        auto& l = t.second;
        while (!l.empty())
        {
            auto f1 = move(l.front());
            auto it = l.erase(l.begin());
            auto c1 = get<1>(f1[0]);
            list<factors> similar;
            while (it != l.end())
            {
                auto& f2 = *it;
                auto c2 = get<1>(f2[0]);
                auto g = gcd(c1, c2);
                auto m1 = c2 / g;
                auto m2 = c1 / g;
                bool compatible = true;
                for (size_t i = 1; i < f1.size(); ++i)
                {
                    if (get<1>(f1[i]) * m1 != get<1>(f2[i]) * m2)
                    {
                        compatible = false;
                        break;
                    }
                }
                if (!compatible)
                {
                    ++it;
                    continue;
                }
                similar.emplace_back(move(f2));
                it = l.erase(it);
            }
            if (similar.empty())
            {
                result += maxB - minB + 1;
                continue;
            }
            unordered_set<int> u;
            similar.emplace_front(move(f1));
            for (auto& t : similar)
            {
                auto m = get<1>(t[0]);
                for (int p = minB; p <= maxB; ++p)
                {
                    u.insert(m * p);
                }
            }
            result += u.size();
        }
    }
    return result;
}

int h(factors const& v)
{
    int h = 1;
    for (auto t : v)
    {
        h *= get<0>(t);
    }
    return h;
}

int gcd(int a, int b)
{
    for (;;)
    {
        int r = a % b;
        if (r == 0) return b;
        a = b;
        b = r;
    }
}

factors factorize(int n) {
    vector<tuple<int, int>> result;
    for (auto p : primes) {
        int count = 0;
        while (n % p == 0)
        {
            ++count;
            n /= p;
        }
        if (count > 0)
        {
            result.push_back(make_tuple(p, count));
        }
        if (p > n) break;
    }
    if (n > 1)
    {
        result.push_back(make_tuple(n, 1));
    }
    return result;
}