Submission

Score: 70

User: gay69

Problemset: Twin, Cousin, and Sexy Prime

Language: cpp

Time: 1.085 second

Submitted On: 2025-10-05 21:11:15

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> find_sieve(ll l, ll r) {
    vector<ll> sieve;
    for (int i = l; i <= r; i++) {
        bool flg = (i >= 2);
        for (ll j = 2; j * j <= i && flg; j++) {
            flg &= (i % j != 0);
        }
        sieve.push_back(flg);
    }
    return sieve;
}

int main() {
    ll l, r;
    cin >> l >> r;
    vector<ll> sieve = find_sieve(max(0ll, l - 6), r + 6);
    r -= max(0ll, l - 6);
    l -= max(0ll, l - 6);
    ll m = sieve.size();
    ll ans = 0, ans2 = 0, ans3 = 0;
    for (int i = max(0ll, l - 6); i <= r + 6; i++) {
        if (i + 2 <= r + 6 && sieve[i] && sieve[i + 2]) {
            ans += (i >= l && i <= r && sieve[i] % 2 != 0);
            ans += (i + 2 >= l && i + 2 <= r && sieve[i + 2] % 2 != 0);
            sieve[i] *= 2;
            sieve[i + 2] *= 2;
        }
        if (i + 4 <= r + 6 && sieve[i] && sieve[i + 4]) {
            ans2 += (i >= l && i <= r && sieve[i] % 3 != 0);
            ans2 += (i + 4 >= l && i + 4 <= r && sieve[i + 4] % 3 != 0);
            sieve[i] *= 3;
            sieve[i + 4] *= 3;
        }
        if (i + 6 <= r + 6 && sieve[i] && sieve[i + 6]) {
            ans3 += (i >= l && i <= r && sieve[i] % 5 != 0);
            ans3 += (i + 6 >= l && i + 6 <= r && sieve[i + 6] % 5 != 0);
            sieve[i] *= 5;
            sieve[i + 6] *= 5;
        }
    }
    cout << ans << "\n" << ans2 << "\n" << ans3 << "\n";
    return 0;
}