Submission

Score: 100

User: colo39

Problemset: Twin, Cousin, and Sexy Prime

Language: cpp

Time: 0.179 second

Submitted On: 2026-10-02 21:59:53

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

class OddBitset {
private:
    vector<unsigned long long> bits;

public:
    explicit OddBitset(int maxValue) {
        size_t numberOfBits = static_cast<size_t>(maxValue / 2 + 1);
        size_t numberOfWords = (numberOfBits + 63) / 64;

        bits.assign(numberOfWords, ~0ULL);
    }

    void setComposite(int x) {
        size_t index = static_cast<size_t>(x / 2);
        bits[index >> 6] &= ~(1ULL << (index & 63));
    }

    bool isPrime(int x) const {
        if (x < 2) {
            return false;
        }

        if (x == 2) {
            return true;
        }

        if ((x & 1) == 0) {
            return false;
        }

        size_t index = static_cast<size_t>(x / 2);
        return (bits[index >> 6] >> (index & 63)) & 1ULL;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, U;
    cin >> L >> U;


    int limit = U + 6;

    OddBitset prime(limit);

    prime.setComposite(1);

    for (int i = 3; 1LL * i * i <= limit; i += 2) {
        if (prime.isPrime(i)) {
            for (long long j = 1LL * i * i; j <= limit; j += 2LL * i) {
                prime.setComposite(static_cast<int>(j));
            }
        }
    }

    int answerTwin = 0;
    int answerCousin = 0;
    int answerSexy = 0;

    for (int p = L; p <= U; p++) {
        if (!prime.isPrime(p)) {
            continue;
        }

        if (prime.isPrime(p - 2) || prime.isPrime(p + 2)) {
            answerTwin++;
        }

        if (prime.isPrime(p - 4) || prime.isPrime(p + 4)) {
            answerCousin++;
        }

        if (prime.isPrime(p - 6) || prime.isPrime(p + 6)) {
            answerSexy++;
        }
    }

    cout << answerTwin << '\n';
    cout << answerCousin << '\n';
    cout << answerSexy << '\n';

    return 0;
}