เลขสมาร์ท (Smart Number) ลำดับที่ N ใน C++

โจทย์

เลขสมาร์ท (Smart number) คือตัวเลขที่มีตัวประกอบเฉพาะที่แตกต่างกันอย่างน้อย 3 ตัว คุณได้รับตัวเลข N หาเลขสมาร์ทลำดับที่ n

ลำดับของเลขสมาร์ทคือ

30, 42, 60, 66, 70, 78...

อัลกอริธึม

กำหนดตัวเลข N
กำหนดตัวนับเป็น 0
เขียนฟังก์ชันตรวจสอบว่าตัวเลขที่กำหนดเป็นเลขเฉพาะหรือไม่
เขียนฟังก์ชันตรวจสอบว่าตัวเลขเป็นเลขสมาร์ทหรือไม่
เขียนลูปที่วนรอบจาก 30 เนื่องจากเลขสมาร์ทแรกคือ 30
- ตรวจสอบว่าตัวเลขปัจจุบันเป็นเลขสมาร์ทหรือไม่โดยใช้ฟังก์ชันเลขเฉพาะ
- เพิ่มตัวนับ 1 เมื่อเจอเลขสมาร์ท
- คืนค่าเลขสมาร์ทเมื่อตัวนับเท่ากับ N

การนำไปใช้งาน

ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน C++

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

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

bool isSmartNumber(int n) { 
    int count = 0; 
    for (int i = 2; i < n; i++) { 
        if (n % i == 0 && isPrime(i)) { 
            count += 1; 
        } 
        if (count == 3) { 
            return true; 
        } 
    } 
    return false; 
} 

int getNthSmartNumber(int n) { 
    int i = 30, count = 0; 
    while (true) { 
        if (isSmartNumber(i)) { 
            count += 1; 
        } 
        if (count == n) { 
            return i; 
        } 
        i += 1; 
    } 
} 

int main() { 
    int N = 25; 
    cout << getNthSmartNumber(N) << endl; 
    return 0; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้