101982B Coprime Integers

    #define ll long long
    #include <bits/stdc++.h>
    using namespace std;

    const int OO = 1e9;
    const double EPS = 1e-9;
    const int MAX = 10000001;
    int mob[MAX];
    int cnt[2][MAX];
    bool is_prime[MAX];

    void pre() {
        for(int i = 0; i < MAX; i++) {
            is_prime[i] = mob[i] = 1;
        }
        is_prime[0] = is_prime[1] = 0;
        for(int i = 2; i < MAX; i++) {
            if(is_prime[i]) {
                mob[i] = -1;
                for(int j = i*2; j < MAX; j+=i) {
                    mob[j] *= -1;
                    is_prime[j] = false;
                    if((j/i)%i == 0) {
                        mob[j] = 0;
                    }
                }
            }
        }
    }

    int main()
    {
        ios_base::sync_with_stdio(NULL);
        cin.tie(0);
        cout.tie(0);
        pre();
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        for(int i = 2; i < MAX; i++) {
            cnt[0][i] += (i >= a && i <= b);
            cnt[1][i] += (i >= c && i <= d);
            for(int j = i*2; j < MAX; j += i) {
                cnt[0][i] += (j >= a && j <= b);
                cnt[1][i] += (j >= c && j <= d);
            }
        }
        ll ans = 1ll*(b-a+1)*(d-c+1);
        for(int i = 2; i < MAX; i++) {
            ans = ans + 1ll * mob[i] * cnt[0][i] * cnt[1][i];
        }
        cout << ans << "\n";
        return 0;
    }