Tìm số tam giác đầu tiên có số ước vượt quá N trong C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ tìm số tam giác (triangular number) đầu tiên có số lượng ước số lớn hơn một số N cho trước.

Khái niệm

Số tam giác là số có dạng tổng các số tự nhiên liên tiếp: 1, 3, 6, 10, 15, 21... (tức là n(n+1)/2).

Các bước thực hiện

1. Khởi tạo N và biến đếm i = 1.
2. Lặp vô hạn cho đến khi tìm thấy số thỏa mãn.
3. Kiểm tra i có phải số tam giác không (bằng cách cộng dồn 1, 2, 3...).
4. Đếm số ước của i.
5. Nếu i là số tam giác VÀ số ước > N, in ra i và dừng.

Mã nguồn ví dụ

#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++;
    }
    return count;
}

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

Kết quả đầu ra

6

Lưu ý tối ưu

Code trên dùng phương pháp vét cạn (brute force). Để tối ưu, có thể dùng công thức: số tam giác thứ k = k(k+1)/2, và đếm ước bằng phân tích thừa số nguyên tố.

Kết luận

Số tam giác đầu tiên có số ước > 2 là 6 (ước: 1, 2, 3, 6). Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.