หาจำนวนสามเหลี่ยมตัวแรกที่จำนวนตัวหารเกิน N ใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหา จำนวนสามเหลี่ยม (Triangular Number) ตัวแรกที่มีจำนวนตัวหาร (divisors) มากกว่า N ที่กำหนด

จำนวนสามเหลี่ยมคืออะไร?

จำนวนสามเหลี่ยมคือจำนวนที่สามารถเขียนในรูปผลรวมของจำนวนธรรมชาติติดกันตั้งแต่ 1 ได้ เช่น 1, 3 (1+2), 6 (1+2+3), 10 (1+2+3+4), ...

สูตร: T_n = n(n+1)/2

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

1. กำหนดค่า N (จำนวนตัวหารขั้นต่ำ)
2. วนลูปหาจำนวนที่ตรงตามเงื่อนไข
3. ตรวจสอบว่าเป็นจำนวนสามเหลี่ยมหรือไม่
4. ตรวจสอบว่าจำนวนตัวหารมากกว่า N หรือไม่
5. ถ้าผ่านทั้งสองเงื่อนไข ให้พิมพ์จำนวนนั้นและหยุด

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

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

bool isTriangular(int n) {
    if (n < 0) return false;
    int sum = 0;
    for (int i = 1; sum <= n; i++) {
        sum += i;
        if (sum == n) return true;
    }
    return false;
}

int divisorsCount(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) count += 1;
    }
    return count;
}

int main() {
    int n = 2, i = 1;
    while (true) {
        if (isTriangular(i) && divisorsCount(i) > 2) {
            cout << i << endl;
            break;
        }
        i += 1;
    }
    return 0;
}

ผลลัพธ์

6

คำอธิบาย: 6 เป็นจำนวนสามเหลี่ยม (1+2+3) และมีตัวหาร 4 ตัว (1, 2, 3, 6) ซึ่งมากกว่า 2

หมายเหตุประสิทธิภาพ

โค้ดนี้ใช้วิธี brute force อาจช้าสำหรับ N ใหญ่ สามารถปรับปรุงได้โดย:

• ใช้สูตร T_n = n(n+1)/2 แทนการวนลูปหาจำนวนสามเหลี่ยม
• หาตัวหารจนถึงรากที่ 2 แทนที่จะวนถึง n
• ใช้การแยกตัวประกอบเฉพาะ (Prime Factorization) คำนวณจำนวนตัวหารเร็วขึ้น

สรุป

โปรแกรมหาจำนวนสามเหลี่ยมตัวแรกที่มีตัวหารเกิน N หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ