Submission

Score: 100

User: porpeang

Problemset: Twin, Cousin, and Sexy Prime

Language: cpp

Time: 0.273 second

Submitted On: 2026-10-08 10:00:48

#include <iostream>
#include <bitset>

using namespace std;

// ขนาดสูงสุดตามเงื่อนไข u <= 70,000,000
const int MAX = 70000005;

// ประกาศ Global Bitset ใช้หน่วยความจำเพียง ~8.35 MB (ไม่เกิน 16 MB)
bitset<MAX> is_prime;

void sieve() {
    is_prime.set(); // ตั้งค่าทุกช่องเป็น true
    is_prime[0] = is_prime[1] = 0;
    
    for (int i = 2; i * i < MAX; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                is_prime[j] = 0;
            }
        }
    }
}

int main() {
    // ปิด synchronization เพื่อเพิ่มความเร็วในการอ่าน/เขียนข้อมูล
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    sieve();

    int l, u;
    if (!(cin >> l >> u)) return 0;

    int tw = 0, cou = 0, se = 0;

    // วนลูปเช็คจำนวนเฉพาะ p แต่ละตัวในช่วง [l, u]
    for (int p = l; p <= u; p++) {
        if (!is_prime[p]) continue;

        // เช็ค Twin Prime (ต่างกัน 2)
        if ((p - 2 >= 2 && is_prime[p - 2]) || (p + 2 < MAX && is_prime[p + 2])) {
            tw++;
        }
        // เช็ค Cousin Prime (ต่างกัน 4)
        if ((p - 4 >= 2 && is_prime[p - 4]) || (p + 4 < MAX && is_prime[p + 4])) {
            cou++;
        }
        // เช็ค Sexy Prime (ต่างกัน 6)
        if ((p - 6 >= 2 && is_prime[p - 6]) || (p + 6 < MAX && is_prime[p + 6])) {
            se++;
        }
    }

    cout << tw << "\n";
    cout << cou << "\n";
    cout << se << "\n";

    return 0;
}