[C]. Tính Tổng Ước Số Nguyên

main

1.Phương Pháp Cơ Bản

Bạn đang xem: [C]. Tính Tổng Ước Số Nguyên

Để tính tổng ước hay đếm ước của một số nguyên N bạn có thể làm cách đơn giản nhất là duyệt các số từ 1 đến N và kiểm tra tính chia hết của N với các số đó.

Đây là cách làm dễ hiểu nhưng lại không tối ưu về mặt thời gian thực thi.

Vì các ước của N thì chỉ nằm trong khoảng [1, N]

Code 1 : Tính tổng ước của N

#include “stdio.h” int tonguoc(int n){ int tong = 0; for(int i = 1; i <= n; i++){ if(n % i == 0){ tong += i; } } return tong; } int main(){ int N = 60; printf(“Tong uoc cua N : %dn”, tonguoc(N)); }

Output :

Tong uoc cua N : 168

Code 2 : Đếm ước của N

#include “stdio.h” int demuoc(int n){ int dem = 0; for(int i = 1; i <= n; i++){ if(n % i == 0){ dem += 1; } } return dem; } int main(){ int N = 60; printf(“So uoc cua N : %dn”, demuoc(N)); }

Output :

So uoc cua N : 12

2. Phương Pháp Tối Ưu 1

Xem thêm : Lỗi xe máy không gương chiếu hậu bị phạt bao nhiêu?

Trong phương pháp cơ bản để tính tổng ước hay đếm ước của số N bạn cần N vòng lặp, bạn có thể cải tiến phương pháp bằng cách duyệt từ 1 tới N / 2.

Giải thích vì sao chỉ cần duyệt tới N / 2 : Các ước của N ngoại trừ chính nó đều nhỏ hơn N / 2 vậy nên ta có thể mặc định là N có ước là chính nó và xét các ước còn lại trong đoạn [1, N / 2].

Ví dụ N = 60 có các ước 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 nhưng ngoại trừ 60 thì các ước còn lại đều nằm trong đoạn [1, N / 2]

Code 1 : Tính tổng ước của N

#include “stdio.h” int tonguoc(int n){ int tong = n; for(int i = 1; i <= n / 2; i++){ if(n % i == 0){ tong += i; } } return tong; } int main(){ int N = 60; printf(“Tong uoc cua N : %dn”, tonguoc(N)); }

Code 2 : Đếm ước của N

#include “stdio.h” int demuoc(int n){ int dem = 1; // n for(int i = 1; i <= n / 2; i++){ if(n % i == 0){ dem += 1; } } return dem; } int main(){ int N = 60; printf(“So uoc cua N : %dn”, demuoc(N)); }

3. Phương Pháp Tối Ưu 2

Trong phương pháp tối ưu 1 để tìm ước của N bạn chỉ cần N / 2 vòng lặp. Phương pháp tối ưu thứ 2 thì bạn chỉ cần duyệt từ 1 tới √N là đủ.

Giải thích : Để tìm được tổng ước hay đếm ước của một số ta cần xét tất cả các ước của N, vậy nếu duyệt từ 1 tới √N thì sẽ không duyệt được các ước lớn hơn √N. Ví dụ với N = 60 thì √N = 7 (lấy số nguyên) sẽ không xét được các ước như 20, 30, 60 ?

Với số tự nhiên N, bạn luôn có thể viết N thành tích của 2 ước của nó. Ví dụ với N bằng 60 thì bạn có thể viết thành 1×60, 2×30, 3×20, 4×15, 5×12, 6×10.

Giả sử viết N = a * b và a ≤ b trong đó a và b tương ứng với 2 ước của N thì chắc chắn a ≤ √N, vì nếu a > √N thì b > √N và khi đó tích của a và b sẽ vượt quá N.

Vậy nên khi xét tất cả các ước của N thì ta chỉ cần xét được ước nhỏ hơn (√N) và từ ước nhỏ hơn đó suy ra được ước còn lại.

Ví dụ với N = 60 :

Xem thêm : Hiến máu có thực sự tốt cho sức khỏe của bạn hay không?

ab160230320415512610

Chú ý : Với N là số chính phương thì sẽ xảy ra trường hợp 2 ước a và b bằng nhau, khi đó bạn chỉ được xét 1 lần.

Ví dụ với N = 16

ab1162844

Code 1 : Tính tổng ước của N

#include “stdio.h” #include “math.h” int tonguoc(int n){ int tong = 0; for(int i = 1; i <= sqrt(n); i++){ if(n % i == 0){ tong += i; // ước thứ 1 if(i != n / i){ tong += n / i; // ước tương ứng } } } return tong; } int main(){ int N = 60; printf(“Tong uoc cua N : %dn”, tonguoc(N)); }

Output :

Tong uoc cua N : 168

Code 2 : Đếm ước của N

#include “stdio.h” #include “math.h” int demuoc(int n){ int dem = 0; // n for(int i = 1; i <= sqrt(n); i++){ if(n % i == 0){ dem += 1; // ước i if(i != n / i){ dem += 1; // ước n / i } } } return dem; } int main(){ int N = 60; printf(“So uoc cua N : %dn”, demuoc(N)); }

Output :

So uoc cua N : 12

KẾT LUẬN : Trong 3 phương pháp trên thì phương pháp thứ 3 tối ưu nhất tuy nhiên cũng sẽ khó hiểu nhất, các bạn nên sử dụng code thứ 3 để tìm ước và tính tổng ước sau khi kết thúc bài học này.

Xem thêm video hướng dẫn của mình về bài toán tính tổng ước :

SnQzrOaR-S4

Nguồn: https://luatduonggia.edu.vn
Danh mục: Tổng hợp