Code sinh cặp số sinh đôi nhỏ hơn một số nguyên dương cho trước 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 ở bài dưới đây, mn có thể giúp mình ko.
Đề bài : Các số nguyên tố sinh đôi (twin prime) là các số nguyên tố mà khoảng cách giữa chúng là 2. Hãy in tất cả cặp số sinh đôi nhỏ hơn một số nguyên dương cho trước (số nguyên dương này < 1000)

#include <iostream>

using namespace std;
bool snt(int a)
{
    if (a<2) return false;
    else if (a==2) return true;
    else
    {
        for (int i=2; i<a ;i++)
            {
                if (a%i==0) {return false;
                break;}
            }
    }
}

int main()
{
    int n,i,u;
    cin>>n;
    u=0;
    i=3;
    while (i+2<n)
    {
        if (snt(i)==true && snt(i+2)==true)
        {
            cout<<i<<", "<<i+2<<endl;
            u++;
        }
        i=i+2;
    }
    cout<<"Tong: "<<u<<" cap so sinh doi < "<<n;
    return 0;
}

Đề bài của bạn khác hẳn với đề bài trong topic kia nên mình move sang topic mới đây.

Trước hết bạn hãy đăng code lên dưới dạng text theo hướng dẫn:

2 Likes

Time Limit Exceeded không phải là lỗi, nó là 1 verdict chấm bài. Code của bạn chỉ bị chạy quá lâu so với thời gian đề bài đặt ra, code không hề chạy lỗi.

Hàm kiểm tra nguyên tố của bạn chạy quá lâu. Để tối ưu hàm kiểm tra nguyên tố, bạn chỉ cần chạy i từ 2 đến \lfloor \sqrt{n} \rfloor là đủ. Lý do vì nếu n có 1 ước i thì n chắc chắn sẽ có ước n / i.


Muốn không bị Time Limit Exceeded bài này, bạn cần sử dụng sàng nguyên tố Eratosthenes.

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