Cải tiến thuật toán kiểm tra số hoàn thiện trong C++

#1

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("\n 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("\n %lld la so hoan thien", n);
	}
	else {

		printf("\n %lld khong phai la so hoan thien", n);
	}

	_getch();
	return 0;
}
#2

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ó.

2 Likes
#3

Hi Lê Hiếu.
Theo mình là như này:

for i = [sqrt(n)]; i > 1; i--:
    if n % i == 0:
       s += i + n / i
       if s > n:
           return false.

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.

3 Likes
#4

Muốn kiểm tra các số thật to mà vẫn ổn thì:

  • Giảm độ phức tạp từ O(n^2) (code của bạn) xuống O(n sqrt(n)): chạy i từ 2 -> sqrt(n), nếu có ước i nào 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.
  • Giảm độ phức tạp xuống O(1): dùng mảng hằng thôi =)) Đó là cách đơn giản và hữu hiệu bởi số hoàn hảo trong khoảng 2^64-1 chỉ đếm trên đầu ngón tay =))
1 Like
#5

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 :slight_smile:

#6

Em cảm ơn anh, cách của anh rất hay ạ :slight_smile:

#7

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

1 Like
#8

Cách cải thiện nhanh nhất là tra bảng :smiley: 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.

2 Likes
#10

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 :laughing: mà ta phải kế thừa nó :yum: 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 :stuck_out_tongue_winking_eye:

1 Like
#11

Ý mình không phải vậy :smiley: 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.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?