ตรวจสอบตัวเลขที่มีตัวประกอบ 4 ตัวแตกต่างกันใน C++

ภาพรวมปัญหา

ได้รับ Q คำถาม แต่ละคำถามมีตัวเลข N ตรวจสอบว่า N มีตัวประกอบที่แตกต่างกันพอดี 4 ตัวหรือไม่

ตัวอย่าง

Input: Q = 3, queries = {4, 6, 15}
Output: NO, YES, YES
Explanation:
4: factors {1,2,4} = 3 ตัว -> NO
6: factors {1,2,3,6} = 4 ตัว -> YES
15: factors {1,3,5,15} = 4 ตัว -> YES

วิธีแก้ปัญหา

วิธีตรวจสอบตัวประกอบ - O(√N)

นับตัวประกอบจาก 1 ถึง √N

วิธีทฤษฎีจำนวน (Number Theory) - O(1) ต่อคำถามหลังการเตรียม

ตัวเลขมีตัวประกอบ 4 ตัวได้ 2 กรณี:

• กำลังสามของจำนวนเฉพาะ: p³ -> ตัวประกอบ {1, p, p², p³}
• ผลคูณของจำนวนเฉพาะ 2 ตัวที่ต่างกัน: p₁ × p₂ -> ตัวประกอบ {1, p₁, p₂, p₁p₂}

คำนวณล่วงหน้าด้วย Sieve of Eratosthenes

ตัวอย่างโค้ด C++ (วิธีที่มีประสิทธิภาพ)

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

int N = 1000;
bool hasFourFactors[1000];

void fourDistinctFactors() {
    bool primeNo[N+1];
    memset(primeNo, true, sizeof(primeNo));
    for (int i = 2; i*i <= N; i++)
        if (primeNo[i])
            for (int j = i*2; j <= N; j += i)
                primeNo[j] = false;
    
    vector primes;
    for (int i = 2; i <= N; i++)
        if (primeNo[i]) primes.push_back(i);
    
    memset(hasFourFactors, false, sizeof(hasFourFactors));
    for (int i = 0; i < primes.size(); i++) {
        int p1 = primes[i];
        if (p1*p1*p1 <= N) hasFourFactors[p1*p1*p1] = true;
        for (int j = i+1; j < primes.size(); j++) {
            int p2 = primes[j];
            if (p1*p2 > N) break;
            hasFourFactors[p1*p2] = true;
        }
    }
}

int main() {
    fourDistinctFactors();
    int Q = 3;
    int query[] = {3, 6, 15};
    for (int i = 0; i < Q; i++) {
        if (hasFourFactors[query[i]])
            cout << "YES ";
        else
            cout << "NO ";
    }
    return 0;
}

ผลลัพธ์

NO YES YES