นับจำนวนในช่วงที่ตัวประกอบเฉพาะมีแค่ 2 และ 3 ใน C++

ภาพรวมปัญหา

ให้ช่วง [START, END] ต้องการนับจำนวนที่ตัวประกอบเฉพาะมีเฉพาะ 2 และ 3 (รูปแบบ 2ᵃ × 3ᵇ)

ตัวอย่าง

Input: START=20, END=25

Output: 1

คำอธิบาย: 24 = 2³ × 3¹

Input: START=1000, END=1500

Output: 4

คำอธิบาย: 1024 (2¹⁰), 1152 (2⁷×3²), 1296 (2⁴×3⁴), 1458 (2¹×3⁶)

แนวทางแก้ปัญหา (Brute Force)

1. วนลูป i จาก START ถึง END
2. หาร i ด้วย 2 และ 3 ซ้ำๆ จนไม่ลงตัว
3. ถ้าเหลือ 1 แสดงว่าตัวประกอบมีแค่ 2 และ 3

โค้ดตัวอย่าง

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

int twothreeFactors(int start, int end) {
    if (start == 1) start++; // 1 ไม่มีตัวประกอบเฉพาะ
    int count = 0;
    for (int i = start; i <= end; i++) {
        int num = i;
        while (num > 1) {
            if (num % 2 == 0) num /= 2;
            else if (num % 3 == 0) num /= 3;
            else break;
        }
        if (num == 1) count++;
    }
    return count;
}

int main() {
    int START = 10, END = 20;
    cout << "Count: " << twothreeFactors(START, END);
    return 0;
}

ผลลัพธ์

Numbers with only 2 and 3 as prime factors: 3

แนวทางที่มีประสิทธิภาพมากกว่า (Generate All)

สร้างจำนวนรูปแบบ 2ᵃ × 3ᵇ ทั้งหมด ≤ END แล้วนับที่ ≥ START

โค้ด Generate All

int twothreeFactors_fast(int start, int end) {
    vector<long long> nums;
    for (long long a = 1; a <= end; a *= 2) {
        for (long long b = a; b <= end; b *= 3) {
            nums.push_back(b);
        }
    }
    sort(nums.begin(), nums.end());
    
    int count = 0;
    for (long long x : nums) {
        if (x >= start && x <= end) count++;
    }
    return count;
}

ความซับซ้อน

ข้อมูลเพิ่มเติม

จำนวนเหล่านี้เรียกว่า 3-smooth numbers หรือ Hamming numbers (ประเภทหนึ่ง)

ลำดับ: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972, 1024...