เลข k-Rough หรือ k-Jagged Number ใน C++

ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมเพื่อตรวจสอบว่าตัวเลขที่กำหนดเป็น k-rough หรือ k-jagged number หรือไม่

ตัวเลขที่ตัวประกอบเฉพาะที่น้อยที่สุดมากกว่าหรือเท่ากับ k ที่กำหนด จะเรียกว่า k-rough หรือ k-jagged number

ขั้นตอนการแก้ปัญหา

• กำหนดตัวเลข n และ k
• หาตัวประกอบเฉพาะทั้งหมดของ n และเก็บในเวกเตอร์
• ดึงองค์ประกอบแรกจากเวกเตอร์มาเปรียบเทียบกับ k เพื่อตรวจสอบว่า n เป็น k-rough หรือ k-jagged number หรือไม่

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

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

bool isPrime(int n) { 
    for (int i = 2; i * i <= n; i++) { 
        if (n % i == 0) { 
            return false; 
        } 
    } 
    return true; 
} 

vector<int> getPrimes(int n) { 
    vector<int> primes; 
    for (int i = 2; i < n; i++) { 
        if (n % i == 0 && isPrime(i)) { 
            primes.push_back(i); 
        } 
    } 
    return primes; 
} 

bool isRoughNumber(int n, int k) { 
    vector<int> primes = getPrimes(n); 
    return primes[0] >= k; 
} 

int main() { 
    int n = 75, k = 3; 
    if (isRoughNumber(n, k)) { 
        cout << n << " is a " << k << " rough number" << endl; 
    } else { 
        cout << n << " is not a " << k << " rough number" << endl; 
    } 
    return 0; 
}

ผลลัพธ์

หากรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้:

75 is a 3 rough number

สรุป

คุณสามารถหลีกเลี่ยงการเก็บตัวเลขเฉพาะทั้งหมดในเวกเตอร์ได้ โดยหาตัวประกอบเฉพาะตัวแรกของ n และเปรียบเทียบกับ k เพื่อได้ผลลัพธ์ที่ต้องการ ให้ลองนำแนวคิดที่คล้ายกันไปปรับใช้เพื่อลดความซับซ้อนของพื้นที่และเวลา

หากมีข้อสงสัยเกี่ยวกับบทช่วยสอนนี้ สามารถถามได้ในส่วนความคิดเห็น