Số Refactorable (số chia hết cho số ước của nó) trong C++

Số Refactorable (còn gọi là số tau) là số nguyên dương n chia hết cho số lượng ước số của nó (ký hiệu τ(n) hoặc d(n)).

Ví dụ

Input: 9 → Output: Là số Refactorable
Ước của 9: 1, 3, 9 (3 ước). 9 % 3 == 0 ✓

Input: 10 → Output: Không phải
Ước của 10: 1, 2, 5, 10 (4 ước). 10 % 4 != 0 ✗

Thuật toán

Đếm số ước của n bằng cách duyệt từ 1 đến √n. Nếu i chia hết n:

• Nếu i² == n → tăng đếm 1 (ước đôi).
• Ngược lại → tăng đếm 2 (cặp ước i và n/i).

Mã nguồn C++

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

bool isRefactorable(int n) {
    if (n <= 0) return false;
    int count = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (i * i == n) count++;
            else count += 2;
        }
    }
    return n % count == 0;
}

int main() {
    int number = 9;
    if (isRefactorable(number))
        cout << "Là số Refactorable";
    else
        cout << "Không phải số Refactorable";
    return 0;
}

Kết quả

Là số Refactorable

Giải thích

Vòng lặp đến √n đếm ước hiệu quả O(√N). Kiểm tra điều kiện chia hết. Các số Refactorable đầu tiên: 1, 2, 8, 9, 12, 18, 24, 36, 40, 56, 60, 72, 80, 84, 88, 96...

Kết luận

Bài viết trình bày khái niệm số Refactorable và thuật toán kiểm tra O(√N) bằng C++. Mã nguồn ngắn gọn, dễ hiểu. Có thể triển khai bằng các ngôn ngữ khác.