Submission

Score: 70

User: gay69

Problemset: Twin, Cousin, and Sexy Prime

Language: cpp

Time: 0.547 second

Submitted On: 2025-10-05 21:02:57

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

vector<ll> find_sieve(ll n) {
    vector<ll> sieve(n + 1, 1);
    sieve[0] = sieve[1] = 0;
    for (ll i = 2; i * i <= n; i++) {
        if (sieve[i] == 0) {
            continue;
        }
        for (ll j = i * i; j <= n; j += i) {
            sieve[j] = 0;
        }
    }
    return sieve;
}

int main() {
    ll l, r;
    cin >> l >> r;
    while (r - l > 1e7) {
        continue;
    }
    vector<ll> sieve = find_sieve(r + 6);
    ll m = sieve.size();
    ll ans = 0, ans2 = 0, ans3 = 0;
    for (int i = max(0, 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;
}