01/10/2018, 10:07
Cải tiến thuật toán kiểm tra số hoàn thiện trong C++
Em muốn cải tiến thuật toán kiểm tra số hoàn thiện để test những số lớn thì phải làm thế nào ạ ?
// Kiểm tra xem số nguyên dương n có phải số hoàn thiện hay không ?
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <conio.h>
int main() {
_int64 n = 0;
do {
printf("
Nhap mot so nguyen duong: ");
scanf("%lld", &n);
} while (n < 1);
_int64 S = 1;
for (_int64 i = 2; i <= n / 2; ++i) {
if (n % i == 0) {
S += i;
}
}
if (S == n) {
printf("
%lld la so hoan thien", n);
}
else {
printf("
%lld khong phai la so hoan thien", n);
}
_getch();
return 0;
}
Bài liên quan
Muốn lớn nữa thì phải có kiểu dữ liệu lớn hơn nữa.
Bên C# mình có kiểu System.Numerics.BigInteger lớn không giới hạn.
Nếu C++ không có thì bạn phải tự viết một class hoặc struct số nguyên lớn, tự định nghĩa các phép toán cho nó.
Hi Lê Hiếu.
Theo mình là như này:
Bạn tìm cách loại các số không thỏa mãn băng cách so sánh tổng s với n sớm. Và tìm các ước từ khoảng căn n trước vì khi đó tổng hai ước là lớn nhất.
Muốn kiểm tra các số thật to mà vẫn ổn thì:
sum += i + n/i. Nhớ trường hợp đặc biệt là n chính phương và sum khởi tạo bằng 1.em chưa học đến C#, class với struct. Em mới chỉ học đến vòng lặp thôi anh ạ ! Chắc khi nào học em sẽ thử cách của anh
Em cảm ơn anh, cách của anh rất hay ạ
Em vừa search gg đúng như anh nói ở ý thứ hai, số hoàn thiện trong khoảng đó chỉ đếm trên đầu ngón tay
Cách cải thiện nhanh nhất là tra bảng tại vì nào giờ người ta chỉ biết có 49 số (chẵn) và không có số lẻ nào dưới 1500 chữ số, kèm những điều kiện khác.
bác rogp10 nói đúng đấy. không nên làm lại cái người ta đã bỏ công sức ra hoàn thiện rồi mà ta phải kế thừa nó vậy bác nên tìm hiểu thuật toán thôi, còn khi triển khai thì làm bậy cái mảng lưu và tra cho nhanh
Ý mình không phải vậy tức là có chừng chục số thỏa mãn thì tra bảng cho rồi.
Để tính tổng ước thì dùng phân tích TSNT là nhanh nhất.
p/s: giờ là 50.