Hỏi cách sửa code bị Time Limit Exceeded

Xin chào mọi người ạ! Hiện tại mình đang gặp lỗi Time Limit Exceeded ở cả hai bài dưới đây

Bài 1: Tìm số đảo ngược cũng là số nguyên tố

using namespace std;
bool nt(int n)
{
    if(n<2) return false;
    for (int i=2;  i<n;  i++)
    { 
        if (n%i==0) return false;
    }
    return true;
}
int Dao(int n)
{
    int x=0;
    do
    {
        x=x*10+n%10;
        n/= 10;
    }
    while(n!=0);
    return x;
}
int main()
{
    int a,b,dem=0;
    cin >> a >> b;
    for(int i=a; i<=b; i++)
    {
        if (nt ( Dao(i)) && nt(i) )
        {
            dem++;
        }
    }
    cout<<dem;
}

Bài 2: Tìm tổng ước chung của 2 số nguyên dương

    using namespace std;
    int input ()
    {
        int a;
        cin >> a;
        return a;
    }

    int input (int &b)
    {
        cin>>b;
        return NULL;

    }

    int TongUocChung(int a, int b)
    {
        int s=0;

        for (int i=1; i<=a && i<=b; i++)
        {
            if(a%i==0 && b%i==0)
                s=s+i;
        }
        return s;
}

int main()
{
    int a, b;
    a = input();
    input(b);
    cout << a << b;
    cout << TongUocChung(a, b);
    return 0;
}

Xin phép được nhờ mọi người hướng dẫn cách khắc phục lỗi, mình xin cảm ơn rất nhiều !

TLE là lỗi chạy quá thời gian cho phép. Làm dạng bài này nên tránh độ phức tạp tuyến tính :kissing:

Ở bài 1, các ước nguyên tố của một số không phải số nguyên tố chỉ nằm trong khoảng [2;\sqrt n]

Ở bài 2 có thể tối ưu nhờ tính chất:

Mọi ước chung của các số là ước của ƯCLN của các só đó
https://vi.m.wikipedia.org/wiki/Ước_số_chung_lớn_nhất

4 Likes

Bài 1 áp dụng tính chất chia hết cho 2, 5 sẽ loại được 3/5 số trường hợp.

Bài 2 tìm ước chung lớn nhất rồi phân tích thừa số nguyên tố ƯCLN để tính tổng.

5 Likes

cho mình hỏi là ở bài 2 mình viết một hàm tìm ước chung lớn nhất rồi làm sao để mình gọi hàm đó vào hàm phân tích thừa số nguyên tố được ạ ? mình thử viết như sau (hàm gcd(a,b) là hàm tìm UCLN)

int TongUocChung(int a, int b)
{
    for(int i = 2; i <= gcd(a,b); i++)
{
    int dem = 0;
    while(gcd(a,b) % i == 0)
    {
        ++dem;
        gcd(a,b) /= i;
    }
    if(dem)
    {
        cout << i;
        if(dem > 1) cout << "^" << dem;
        if(gcd(a,b) > i)
        {
            cout << " * ";
        }
    }
}

}

thì bị báo lỗi ở dòng gcd(a,b) /= i;
mong được giải đáp ạ

Bạn có thể nói cụ thể bài 1 cho mình với được không ạ?

Cú pháp gì đây bạn?
Ở phép gán (=, +=, -=, *=, /=,...), bên trái luôn phải là 1 biến. Bạn gán giá trị cho 1 hàm?

Xét n có phải số nguyên tố không, thì chỉ chạy vòng lặp từ 2 đến sqrt(n) thôi. Cái này là suy luận toán cơ bản.

Tính căn thì cách đơn giản nhất là chia nhị phân :slight_smile: căn cứ vào giới hạn của bài, hoặc lấy (int)(1.4142*1<<15).

2 Likes

Bạn tạo 1 biến là được mà :neutral_face:

A post was split to a new topic: Code sinh cặp số sinh đôi nhỏ hơn một số nguyên dương cho trước bị Time Limit Exceeded

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