1. Thuật Toán Cơ Bản
Số hoàn hảo là số mà tổng các ước thực sự của nó (không tính chính nó) bằng chính nó. Ví dụ N = 28 có các ước 1, 2, 4, 7, 14, 28 thì các ước thực sự là 1, 2, 4, 7, 14 có tổng cũng bằng 28 nên 28 là số hoàn hảo
Để kiểm tra N là số hoàn hảo bạn chỉ cần tính tổng ước của N sau đó loại bỏ ước N và so sánh với N
Code 1 :
#include "stdio.h" #include "math.h" int is_perfect(int n){ int tong = 0; for(int i = 1; i <= sqrt(n); i++){ if(n % i == 0){ tong += i; if(i != n / i){ tong += n / i; } } } if(tong - n == n){ return 1; } return 0; } int main(){ int n = 1000; for(int i = 1; i <= n; i++){ if(is_perfect(i)){ printf("%d ", i); } } return 0; }
Output :
6 28 496
Code trên tính tổng ước của N sau đó trừ đi chính nó vì ta đang muốn tính các ước mà không xét chính nó.
Bạn cũng có thể bỏ qua ước 1 để không xét ước N như sau, nhưng chú ý khi N = 1
Code 2 :
#include "stdio.h" #include "math.h" int is_perfect(int n){ int tong = 1; for(int i = 2; i <= sqrt(n); i++){ if(n % i == 0){ tong += i; if(i != n / i){ tong += n / i; } } } if(tong == n && n != 1){ return 1; } return 0; } int main(){ int n = 1000; for(int i = 1; i <= n; i++){ if(is_perfect(i)){ printf("%d ", i); } } return 0; }
2. Định Lý Euclid - Euler
Để kiểm tra số hoàn hảo bạn có thể sử dụng code ở mục 1, tuy nhiên nó chỉ phù hợp khi số N bạn cần kiểm tra ≤ 1012. Trong trường hợp cần kiểm tra số N lên tới 1018 thì code trên chạy rất lâu mới ra kết quả.
Bạn thử viết hàm kiểm tra số hoàn hảo như mục 1 với số long long và thử chạy với N = 1018 để kiểm tra.
Phương pháp tối ưu hơn để kiểm tra số hoàn hảo đó là sử dụng định lý Euclid - Euler. Định lý này phát biểu như sau
Nếu p là số nguyên tố và 2p - 1 cũng là số nguyên tố thì : 2p-1 * (2p - 1) sẽ là một số hoàn hảo.
Ví dụ :
p = 2 là số nguyên tố, và 22 - 1 cũng là số nguyên tố nên : 22-1 * (22 - 1) = 6 là số hoàn hảo
p = 3 là số nguyên tố, và 23 - 1 cũng là số nguyên tố nên : 23-1 * (23 - 1) = 4 * 7 = 28 là số hoàn hảo
Vậy để kiểm tra được hết các số hoàn hảo từ 1 tới giới hạn lớn nhất của số long long (9.1018) thì bạn cần duyệt các số nguyên tố p lớn tới đâu ?
Nhận thấy tích 2p-1 * (2p - 1) ~ 22p sẽ phải lên tới 9.1018 ~ 263 => 2p ~ 63 nên bạn chỉ cần duyệt p tới 32, 33 là đủ rồi.
Code này sẽ sinh ra tất cả các số hoàn hảo từ 1 tới 9.1018 và so sánh với N
Code :
#include "stdio.h" #include "math.h" int prime(long long n){ if(n < 2){ return 0; } for(int i = 2; i <= sqrt(n); i++){ if(n % i == 0 ) return 0; } return 1; } int is_perfect(long long n){ for(int p = 1; p <= 33; p++){ if(prime(p)){ long long tmp1 = pow(2, p) - 1; if(prime(tmp1)){ long long tmp2 = pow(2, p - 1); if(tmp1 * tmp2 == n){ return 1; } } } } return 0; } int main(){ int n = 1000; for(int i = 1; i <= n; i++){ if(is_perfect(i)){ printf("%d ", i); } } return 0; }
Output :
6 28 496
Bạn cũng có thể in ra các số hoàn hảo từ 1 tới 9.1018
#include "stdio.h" #include "math.h" int prime(long long n){ if(n < 2){ return 0; } for(int i = 2; i <= sqrt(n); i++){ if(n % i == 0 ) return 0; } return 1; } void print_perfect(){ for(int p = 1; p <= 33; p++){ if(prime(p)){ long long tmp1 = pow(2, p) - 1; if(prime(tmp1)){ long long tmp2 = pow(2, p - 1); printf("%lld\n", tmp1 * tmp2); } } } } int main(){ print_perfect(); return 0; }
Output :
6 28 496 8128 33550336 8589869056 137438691328 2305843008139952128
Nhận xét : từ 1 tới 9.1018 cũng chỉ có 8 số hoàn hảo.
Xem thêm bài giảng về Số Hoàn Hảo của mình :
