Quá thời gian khi tìm số nguyên tố đảo

em không biết em đăng post có đúng không nhưng hãy chỉ giáo em với … em có đề bài này và giải gặp lỗi Time Limit Exceeded các cao nhân giúp em được không ạ ? . em xin cảm ơn
Có một vài số nguyên tố khi viết đảo lại nó cũng là số nguyên tố. Ví dụ như 17 hay 71 đều là số nguyên tố. Cho hai số a và b hãy tìm xem có bao nhiêu số x nằm trong đoạn [a, b] sao cho khi viết xuôi hay viết đảo số đó đều là số nguyên tố.
INPUT : hai số nguyên dương a, b (a <= b)
OUTPUT : Số lượng số x

coce của em :

using namespace std;
int sdn(int n)
{
    int k=0;
    while(n!=0){
    k=k*10+n%10;
    n/=10;
    }
    return k;
}
 
bool kt(int N)
{
    if (N<2) return false;
    if ((N!=2)&&(N%2==0)) return false;
    for (int i = 2; i <= N/2; i++)
    {
        if (N % i == 0)
            return false;
    }
    return true;
}
 
int main()
{
    int i,a,b,s=0;
    cin>>a>>b;
    for(i=a;i<=b;++i){
       if(kt(i) && kt(sdn(i)))
            s+=1;
    }
    cout<<s;
    return 0;
}

Chạy đến sqrt(N) là đủ rồi.

1 Like

Có thể loại theo dải số bắt đầu bằng 2, 4, 6, 8. Sau đó chia thành từng đoạn để sàng.

Coi vậy chứ bài này nhiều đường tính.

2 Likes

anh đã sửa được chưa, em cũng bị thế mà chưa khắc phục được

Đầu tiên sửa lại thành i <= sqrt(n). Tiếp theo chỉ xét số đứng đầu bằng 1 3 5 7 9.

Thực ra bài này sàng phân đoạn mới nhanh.

3 Likes

bài tập không cho dùng thư viện thêm anh ơi, không được dùng sqrt

Thay vào đó thì chặt nhị phân với y = x*x với y trong [1, giới hạn của đề], từ đó bạn tính ra x_high để khởi động quá trình.

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