Trong bài viết này mình sẽ hướng dẫn các bạn tìm tổng ước và đếm ước của một số nguyên, một kiến thức cơ bản trong lập trình

NỘI DUNG :

• Phương Pháp Cơ Bản
• Phương Pháp Tối Ưu 1
• Phương Pháp Tối Ưu 2
• Video Tutorial

  ---

main

1.Phương Pháp Cơ Bả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 : %d\n", 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 : %d\n", demuoc(N));  

}

Output :

So uoc cua N : 12

---

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

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 : %d\n", tonguoc(N));  

}

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

include "stdio.h"

int demuoc(int n){

int dem = 1;   
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 : %d\n", 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 1x60, 2x30, 3x20, 4x15, 5x12, 6x10.

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.