Thuật toán kiểm tra số hoàn hảo trong C / C++

Trong bài viết này, codehow sẽ giới thiệu đến cá bạn thuật toán kiểm tra số hoàn hảo trong C / C++. Đây chắn hẳn là một khái niệm mới đối với các bạn mới bắt đầu học lập trình.

Ở toán học phổ thông trước đây mình cũng chưa từng nghe qua khái niệm này. Tuy nhiên khi bắt đầu học lập trình thì mình ngày càng khai phá được nhiều khái niệm hay hơn. Vậy hãy bắt đầu tìm hiểu cùng mình thôi nhé.

Số hoàn hảo là gì?

Nếu khái niệm hơi khó hiểu, các bạn có thể xem ví dụ dưới đây để hiểu rõ hơn nhé.

Ví dụ: Mình có số 6 là số hoàn hảo, bởi vì 6 có 3 ước số là 1, 2 , 3. Vậy tổng các ước số là 1 + 2 + 3 = 6 (bằng chính nó).

Ví dụ: Số 10 không phải là số hoàn hảo vì ước của 10 là 1, 2, 5. Tổng của nó là 8 chứ không phải 10.

Công thức:

Một số tính chất đặc biệt của số hoàn hảo:

• Là các số chẵn.
• Có 4 số hoàn hảo đầu tiên là: 6, 28, 496, 8128.

Đến nay vẫn chưa có nghiên cứu nào chứng minh rằng số hoàn hảo là một dãy số vô hạn.

Thuật toán kiểm tra số hoàn hảo trong C / C++

Dưới đây là thuật toán kiểm tra số hoàn hảo trong C / C++, các bạn hãy cùng xem qua thuật toán rồi mình sẽ giải thích ngay bên dưới nhé.

bool check(int a){
    int sum = 0;//khai báo biến sum
    for(int i=1;i<=a/2;i++){ //tạo vòng lặp for để tìm ước số của a
        if(a%i==0) 
            sum+=i; //tổng các ước số của a
    }
    if(sum==a) return true; // trả về true
    return false; // ngược lại trả về false
}

Giải thích thuật toán:

1. Khai báo biến sum = 0, đây là biến để lưu tổng các ước số của số cần kiểm tra.
2. Sử dụng vòng lặp for lặp từ 1 đến a / 2 để tìm ra ước số của a. (vì ước của một số luôn nhỏ hơn nửa số đó, vậy nên điểm dừng vòng lặp là a / 2).
3. Mỗi lần tìm thấy ước số của a, ta cộng dồn vào biến sum.
4. Kiểm tra nếu sum = a (bằng chính nó) thì kết luận đây là số hoàn hảo. Ngược lại thì không phải số hoàn hảo.

Nếu các bạn không sử dụng vòng lặp for, thì có thể sử dụng vòng lặp while để thay thế nhé.

bool check(int a){
    int sum = 0, i = 1;//khai báo biến sum
    while(i<=a/2){ //tạo vòng lặp while để tìm ước số của a
        if(a%i==0) 
            sum+=i; //tổng các ước số của a
            i++; // bước nhảy của vòng lặp while
    }
    if(sum==a) return true; // trả về true
    return false; // ngược lại trả về false
}

Ví dụ thuật toán kiểm tra số hoàn hảo trong C / C++

Dựa vào thuật toán kiểm tra số hoàn hảo ở trêm, mình sẽ thực hiện một chương trình kiểm tra số hoàn hảo do người dùng nhập vào. Chương trình sẽ được viết bằng hai ngôn ngữ khác nhau là C và C++, các bạn có thể tham khảo nhé.

Chương trình C:

#include <stdio.h>
#include <stdbool.h>
bool check(int a){
    int sum = 0;//khai báo biến sum
    for(int i=1;i<=a/2;i++){ //tạo vòng lặp for để tìm ước số của a
        if(a%i==0) 
            sum+=i; //tổng các ước số của a
    }
    if(sum==a) return true; // trả về true
    return false; // ngược lại trả về false
}

int main(void) {
  int n;
    printf("Nhập vào số cần kiểm tra: ");
    scanf("%d", &n);
    if (check(n)){
        printf("%d là số hoàn hảo.",n);
    }
    else {
        printf("%d không phải là số hoàn hảo.",n);
    }

  printf("\n----------------------------------\n");
  printf("Chương trình này được đăng tại codehow.net");
  return 0;
}

Kết quả:

Chương trình C++:

#include <iostream>
using namespace std;

bool check(int a){
    int sum = 0;//khai báo biến sum
    for(int i=1;i<=a/2;i++){ //tạo vòng lặp for để tìm ước số của a
        if(a%i==0) 
            sum+=i; //tổng các ước số của a
    }
    if(sum==a) return true; // trả về true
    return false; // ngược lại trả về false
}

int main() {
  int n;
    cout << "Nhập vào số cần kiểm tra: ";
    cin >> n;
    if (check(n)){
        cout <<n<< " là số hoàn hảo.";
    }
    else {
        cout <<n<< " không phải là số hoàn hảo";
    }

  cout<<"\n----------------------------------\n";
  cout<<"Chương trình này được đăng tại codehow.net";
  return 0;
}

Kết quả:

Như vậy là chúng ta đã cùng nhau tìm hiểu về thuật toán kiểm tra số hoàn hảo trong C / C++. Hãy luyện tập thật nhiều để nâng cao tư duy logic và sử dụng các thuật toán một cách thành thạo nhé. Chúc các bạn thành công !!!