Số hoàn hảo là gì? một số bài toán tìm số hoàn hảo

Khi tiếp cận với lập trình thì bài toán tìm số hoàn hảo là một trong số các bài toán được xem là bài căn bản và kinh điển của lập trình. Hôm nay chúng ta sẽ cũng tìm hiểu về chủ đề này.

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

Một số được gọi là số hoàn hảo nếu đó là một số nguyên dương và có tổng các ước của nó bằng chính nó.

Ví dụ 6=1+2+3=1*2*3

Ngoài ra số hoàn hảo chẵn còn có công thức: Nếu là số nguyên tố thì  2^n-1(2ⁿ -1)=> là số hoàn chỉnh (hoàn hảo)

Ví du: 6 là số hoàn hảo tương ứng với n=2.

Một số ví dụ về bài toán tìm số hoàn hảo.

Ví dụ 1: Nhập một số nguyên dương từ bàn phím và kiểm tra xem đó có phải là số hoàn hảo hay không.

Thuật toán: Tìm các ước của số vừa nhập và kiểm tra xem tổng của các ước có bằng số vừa nhập hay không.

Code C/C++:

#include<stdio.h>
#include<conio.h>
#include<math.h>
void main()
{
	int x;
	printf("Nhap mot so nguyen duong \n");
	scanf("%d", &x);
	int s = 0;
	for (int i = 1; i < x; i++) 
/* chạy từ 1 đến < x vì không thể chia cho 0 và vì x%x =0 
nhưng x không thể là ước của x */
	if (x%i == 0)
		s += i;
	if (s == x)
		printf("%d la so hoan hao", x);
	else
		printf("%d khong phai la so hoan hao", x);
	getch();
}

Kết quả:

Nhap mot so nguyen duong

4

4 khong phai la so hoan hao

Nhap mot so nguyen duong

6

6 la so hoan hao

Ví dụ 2: Tìm và xuất ra màn hình tất cả các số hoàn hảo có trong một khoảng [A,B].

Thuật toán: 

Kiểm tra từ A=>B, nếu số nào thỏa mãn là số hoàn hảo thì xuất ra màn hình.

Để kiểm tra thì chúng ta cần có 1 hàm kiểm tra số hoàn hảo.

Code C/C++:

Hàm kiểm tra.

int KTSHH(int n)
{
	int s = 0;
	for (int i = 1; i < n; i++) 
	if (n%i == 0)
		s += i;
	if (s == n)
		return 1; // đúng trả về 1
	else
		return 0; // sai trả về 0
}

Hàm liệt kê số hoàn hảo có trong 1 khoảng [A,B] (Xem tiếp ở trang sau)