Code tìm tổng ước số nguyên tố chung bị chạy quá lâu

[SonTung]

Bài toán tìm tổng ước số nguyên tố chung nếu không có trả về -1

Em làm function như này thì bị báo lỗi TLE ạ , làm sao để khắc phục ạ

[rogp10]

0. <= sqrt(n) thôi nhé.
1. Thay đổi thuật toán tìm ước thành theo phân tích thừa số nguyên tố.
2. Đầu tiên lấy ước chung (thuật toán Euclid) rồi mới phân tích thừa số nguyên tố của nó.
3. Giờ mới xác định đk ntn sẽ dẫn đến -1.

[noname00 (HK boy)]

tại sao bạn kiểm tra i == UCLN(m, n) vậy?

Về mặt toán học, các ước chung của m và n có quan hệ như thế nào với UCLN(m, n)?

[noname00 (HK boy)]

Bạn tạo thêm 1 vector chứa tất cả các số nguyên tố bạn đã sinh ra để sử dụng tiếp, không cần phải for i từ 2 đến m nữa.

[SonTung]

Em đã tự giải được rồi ạ , em xin cảm ơn

[Hoang_Van1 (Hoàng Văn)]

E cũng bị TLE chưa khắc phục được, mọi người có thể giúp e được ko :((

#include <iostream>
#include <cmath>
using namespace std;
bool nt(int n)
{
    int i;
    if (n<2) return false;
    for (i=2;i<=sqrt(n);i++)
        if (n%i==0)
        return false;
    return true;
}
int main()
{
    long n,m;
    long t=0;
    int i;
    cin>>n>>m;
    for (i=2; i<=m ; i++)
    if (nt(i)&& n%i==0 && m%i==0) t+=i;
    if (t==0) cout<<"-1";
    else cout<<t;
    return 0;
}

[noname00 (HK boy)]

Trước hết, nếu 1 số p là ước nguyên tố chung của m và n thì có nghĩa p là ước nguyên tố của gcd(m, n).

Bạn cần tính gcd(m, n) trước để giảm bớt độ phức tạp của bài toán.