Tổng đệ quy các chữ số của số nguyên - kiểm tra số nguyên tố bằng C++

Cho số nguyên number. Tính tổng các chữ số, lặp lại cho đến khi được số 1 chữ số (digital root). Kiểm tra số cuối cùng có phải nguyên tố không (2, 3, 5, 7).

Ví dụ

Input: 12341 → 1+2+3+4+1=11 → 1+1=2 → PRIME
Input: 1664 → 1+6+6+4=17 → 1+7=8 → NOT PRIME

Quan sát quan trọng

Tổng đệ quy các chữ số (digital root) của N bằng N % 9 (nếu N % 9 != 0) hoặc 9 (nếu N % 9 == 0 và N > 0). Chỉ cần tính digital root một lần.

Mã nguồn C++

#include <iostream>
using namespace std;

int digitalRoot(int n) {
    if (n == 0) return 0;
    if (n % 9 == 0) return 9;
    return n % 9;
}

void checkPrimeDigitalRoot(int number) {
    int dr = digitalRoot(number);
    cout << "Tổng đệ quy chữ số: " << dr << " - ";
    if (dr == 2 || dr == 3 || dr == 5 || dr == 7)
        cout << "NGUYÊN TỐ";
    else
        cout << "KHÔNG NGUYÊN TỐ";
}

int main() {
    int number = 5555;
    checkPrimeDigitalRoot(number);
    return 0;
}

Kết quả

Tổng đệ quy chữ số: 2 - NGUYÊN TỐ

Giải thích

Hàm digitalRoot tính gốc số (digital root) bằng công thức modulo 9 trong O(1). Sau đó kiểm tra xem kết quả có trong {2,3,5,7} không. Rất nhanh, không cần vòng lặp.

Kết luận

Bài viết giải quyết bài toán kiểm tra tổng đệ quy chữ số có phải nguyên tố bằng công thức digital root O(1). Mã C++ ngắn gọn, hiệu quả. Áp dụng được cho các ngôn ngữ khác.