Tính tổng ước trong c++

Có 2 hàm tính tổng ước, nhận xét tốc độ của từng hàm

Hàm tính tổng ước thứ 1

long long tonguoc(long long n)

{

    long long tong = 0;

    for (long long i = 1; i <= n / i; i++)

    {

        if (n % i == 0)

        {

            tong += i;                

            if (i != n / i)

                tong += n / i;

        }

    }

    return tong;

}

Hàm tính tổng ước thứ 2

long long tonguoc(long long n)

{

    long long tong = 0;

    for (long long i = n; i >= 1; i--)

    {

        if (n % i == 0)

            tong += i;

    }

    return tong;

}

Giải thích hàm tổng ước thứ 1 

1. Cách tìm các ước của 36

Một số là ước của 36 nếu 36 chia hết cho số đó. Các cặp ước của 36 là:

• 1 và 36 vì 1 × 36 = 36 , 36 × 1= 36
• 2 và 18 vì 2 × 18 = 36,  18 x 2 = 36
• 3 và 12 vì 3 × 12 = 36 , 12 x 3 = 36
• 4 và 9 vì 4 × 9 = 36, 9 x 4 = 36
• 6 và 6 vì 6 × 6 = 36, 6 x x6 = 36

Chú ý: Số 6 là điểm giữa vì 6 × 6 = 36. Sau khi tìm được cặp 6 và 6, các cặp ước còn lại đã được tìm thấy trước đó.

2. Hàm tính tổng ước

long long tonguoc(long long n)

{

    long long tong = 0;

    for (long long i = 1; i <= n / i; i++)

    {

        if (n % i == 0)

        {

            tong += i;
            if (i != n / i)

                tong += n / i;

        }

    }

    return tong;

}

3. Giải thích từng bước với n = 36

Bước 1: i = 1

1 <= 36 / 1
1 <= 36  // Đúng

36 chia hết cho 1. Cộng cả 1 và 36 vào tổng. tong = 1 + 36 = 37.

Bước 2: i = 2

2 <= 36 / 2
2 <= 18  // Đúng

36 chia hết cho 2. Cộng cả 2 và 18. tong = 37 + 2 + 18 = 57.

Bước 3: i = 3

3 <= 36 / 3
3 <= 12  // Đúng

Cộng cả 3 và 12. tong = 57 + 3 + 12 = 72.

Bước 4: i = 4

4 <= 36 / 4
4 <= 9  // Đúng

Cộng cả 4 và 9. tong = 72 + 4 + 9 = 85.

Bước 5: i = 5

5 <= 36 / 5
5 <= 7  // Đúng

Nhưng 36 % 5 != 0 nên 5 không phải là ước của 36. Không cộng gì vào tổng.

Bước 6: i = 6

6 <= 36 / 6
6 <= 6  // Đúng

36 chia hết cho 6 nên cộng 6. tong = 85 + 6 = 91. Tiếp theo, chương trình kiểm tra:

if (i != n / i)

Thay số vào:

if (6 != 36 / 6)
if (6 != 6)

Điều kiện sai nên không cộng thêm 6 lần nữa.

Bước 7: i = 7

7 <= 36 / 7
7 <= 5  // Sai

Vòng lặp kết thúc. Hàm trả về kết quả 91.

4. Tại sao không dùng i < n?

Nếu viết:

for (long long i = 1; i < n; i++)

Với n = 36, chương trình phải xét các số từ 1 đến 35, tổng cộng 35 lượt. Nếu viết:

for (long long i = 1; i <= n / i; i++)

Với n = 36, chương trình chỉ xét các số từ 1 đến 6, tổng cộng 6 lượt. Lý do: Khi xét một ước nhỏ i, chương trình cộng luôn ước lớn n / i. Ví dụ, khi i = 4, chương trình đã cộng cả 4 và 9, nên không cần xét lại 9.

5. Tại sao phải dùng dấu <= thay vì dấu <?

Khi n = 36 và i = 6:

i <= n / i
6 <= 6  // Đúng

Chương trình tiếp tục chạy và cộng ước 6. Nếu dùng:

i < n / i
6 < 6  // Sai

Vòng lặp dừng trước khi xử lý i = 6. Ước 6 bị bỏ sót, kết quả chỉ còn 85 thay vì 91.

6. Ghi nhớ

• i <= n / i giúp duyệt đến căn bậc hai của n.
• Mỗi ước nhỏ i giúp tìm được ước lớn n / i.
• i != n / i giúp tránh cộng một ước hai lần khi hai ước bằng nhau.
• Dùng dấu <= để không bỏ sót ước ở giữa khi n là số chính phương, chẳng hạn 16, 25, 36, 49.

Kết luận: Với n = 36, hàm chỉ cần xét i từ 1 đến 6 để tìm đủ các ước và tính được tổng bằng 91.