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

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 ạ

  1. <= sqrt(n) thôi nhé.
  2. Thay đổi thuật toán tìm ước thành theo phân tích thừa số nguyên tố.
  3. Đầ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ó.
  4. Giờ mới xác định đk ntn sẽ dẫn đến -1.
7 Likes

:man_facepalming: 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)?

3 Likes

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.

4 Likes

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

1 Like

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;
}

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.

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?