Cần giúp tăng tốc bài toán hơn ạ!

Thử chạy đến n/2 xem …

Vẫn thế anh ơi… Nó cũng đc 50/100 thôi à :((

Xác định xem số đó là chẵn hay lẻ rồi chạy vòng lặp với step = 2 xem.
p/s: ko biết với C++ thì có nhanh hơn ti nào ko :))

Vẫn như cũ…

Bạn có thể chạy tới căn n. Sau đó tìm 1 lần 2 ước = cách lấy n / i ra ước t2.
Cẩn thận trường hợp i^2 = n

Bạn chỉ cần chạy tới sqrt(n).
Nếu i là ước của n thì n/i cũng là ước của n.
Độ phức tạp là O(sqrt(n)).

À, như bác @drgnz nói =)))

Cách này chắc là lâu hơn :))
https://maytinhbotui.vn/Forums/Topic/cong-thuc-tinh-tong-cac-uoc-cua-mot-so

> #include <iostream>
> #include <math.h>
> using namespace std;
> int main()
> {
> 	int n, s = 0;
> 	cin >> n;
> 	for (int i = 1; i <= sqrt(n); i++)
> 		if (n%i == 0)
> 			s += (i + n / i);
> 	cout << s;
> 	return 0;
> }

Đây ạ. Chạy tới căn n. Nhưng nó vẫn tính luôn n trong đó :((

Các ước số của n không vượt quá căn bậc 2 của n nên bạn xét đến căn bậc 2 của n thôi nha.

Nếu n chính phương thì phải trừ lại đó thôi thì ghi i < sqrt(n) rồi xét riêng.

Để không dính n thì chạy từ 2 lên rồi khởi tạo s = 1.

Các ước số của n không vượt quá căn bậc 2 của n nên bạn xét đến căn bậc 2 của n thôi nha.

Câu này ko chuẩn thực ra nó ntn:

Với mọi hợp số luôn có d | n sao cho 1 < d < n. Nếu 1 < d <= sqrt(n) thì không nói gì. Ngược lại, n > d > sqrt(n) <=> 1/n < 1/d < 1/sqrt(n) <=> 1 < n/d < n/sqrt(n) = sqrt(n). Mà d | n vậy n/d là số nguyên (tính chất phép chia) và (n/d) | n.

Hay nói cách khác, d với n/d là một cặp và một trong hai không vượt quá sqrt(n). Vậy mới ổn.

Cách này dùng để duyệt thôi. Nếu muốn tối ưu thì phân tích ra TSNT rồi tính

#include <iostream>
using namespace std;
int main()
{
    int n, s = 0;
    cin >> n;
    for (int i = 1; i < n; i++)
        if (n%i == 0)
            s = s + i;
    cout << s;
    return 0;
}

#include <iostream>
using namespace std;
int main() {
    int n, s = 0;
    int pre = 1;
    cin >> n;
    for (int i = 2; i < n / 2; i++) {
        while (n % i == 0) {
            n = n / i;
            pre = pre * i;
            sum = sum + pre;
        }
    }

    if (n == i && sum > pre) {
        sum = sum - pre;
    }

    cout << s;
    return 0;
}

Bài toán có hiệu quả khi n lớn. Vậy nên nếu muốn chơi bời hơn thì có thể như sau:

#include <iostream>
using namespace std;
int main() {
    int n = 0;
    int sum = 0;

    cin >> n;
    if (n > 2*2*2*2*2) {
        sum = blad(n);
    } else {
        sum = bladblad(n);
    }

    if (n == i && sum > pre) {
        sum = sum - pre;
    }

    cout << s;
    return 0;
}

int blad (int n) {
    int sum = 0;
    int pre = 1;
    cin >> n;
    for (int i = 2; i < n / 2; i++) {
        while (n % i == 0) {
            n = n / i;
            pre = pre * i;
            sum = sum + pre;
        }
    }

    if (n == i && sum > pre) {
        sum = sum - pre;
    }

    return sum
}

int bladblad (int n) {
    int sum = 0;
    for (int i = 2; i < n / 2; i++) {
        if (n % i == 0) {
            sum = sum + i;
        }
    }

    return sum;
}

Câu hỏi là tổng đó có cấp nhận số 1 không? Đang mặc định là anh không lấy số 1 còn em thì có.
Anyway là bài này đúng là phải phân tích ra thừa số nguyên tố mà quên mất thuật toán đó rồi nên em tự tìm lại thuật toán đó nhé. Cơ mà có lẽ dùng cách này sẽ nhanh hơn thì phải.

Vẫn sqrt(n) được. Chỉ cần xét sau cùng n có bằng 1 không.

Nếu n bằng 1 thì thừa số cuối cùng có số mũ > 1, vì ta biết rõ chia đến sqrt() là đủ. (và ngược lại)
Nếu n khác 1 thì rõ ràng ta vừa chạy xong test cho n, vậy n nguyên tố.

Tks mod nhiệt liệt và cật lực từ bên congdongcviet tới tận đây.!
Mình đã làm ra rồi ạ! Cảm ơn tất cả mọi người

Nếu tính tổng ước n(trừ n) Thì vẫn lấy số 1 anh ơi. VÌ mọi số chia cho nó đều hết mà

Chính xác. Nhưng chú ý chút: nên viết for(i=2; i<x; ++i) rồi cập nhật lại x để tránh phép tính số thực.

Thuật toán tính tổng các ước của 1 số nguyên dương?

Chưa hiểu ý đồ đoạn này lắm…

Một dạng quy nạp đấy c/m tổng ước của n bằng tích tổng ước các thừa số nguyên tố của n, hay S(p1^j1 * p2^j2 * …) = S(p1^j1) * S(p2^j2) * … với p1, p2… nguyên tố và đôi một khác nhau.

Đầu tiên đương nhiên S(p1^j1) = S(p1^j1) rồi. Xét n’ = n * p_i^j_i với gcd(p_i, n) = 1 ta có d | n <=> p_i^k*d | p_i^k*n (với k = [0.. j_i]) => p_i^k*d | p_i^j_i*n. Tức là các ước của n’ có dạng p_i^kd. Cộng lại:
sigma(k=0…j_i) sigma(d | n) (p_i^kd)
= sigma(k=0…j_i) (p_i^k * sigma(d | n)(d))
= sigma(k=0…j_i) (p_i^k * S(n))
= S(n) * sigma(k=0…j_i) (p_i^k)
= S(n) * S(p_i^j_i)

Suy ra đpcm.

gcd(p_i, n) = 1 là vì nếu p_i | n thì khi nhân vào sẽ không phân biệt được p_i^k*P-i và p_i^(k+1), tức là bị dư.

VD: S(2) = 1+2 = 3, nếu nhân bừa thì S(22) =? 33 = 9 (SAI) vì ước của 4 là {1, 2, 4} chứ không phải {1, 2, 21, 22}.

Phân tích ra TSNT lâu hơn việc for các ước mà bạn ?

Sai còn nhanh hơn là khác.

• Nếu là số nguyên tố thì bạn chia tới căn n là xong, như nhau.
• Nếu là hợp số dạng pq thì bạn sẽ chia tới căn q thay vì căn pq (nhanh hơn).
• Nói chung càng nhiều thừa số thì càng nhanh, do số bị chia giảm qua mỗi thừa số tìm được.