全部TLE，大佬救我！

littlewhite_ @ 2023-08-15 11:00:43

#include <bits/stdc++.h>
using namespace std;

int dislocation(int x)
{
    int y = x;
    int cnt = 0;
    while (y >= 0)
    {
        y /= 10;
        cnt++;
    }
    return cnt;
}

bool is_palindrome(int n)
{
    int ans = 0;
    int res = n;
    for (int i = 1; i <= dislocation(n); i++)
    {
        ans = ans * 10 + n % 10;
        n /= 10;
    }
    if (ans == res)
    {
        return true;
    }
    else
    {
        return false;
    }
} 

bool is_prime(int x)
{
    if (x == 0) 
    {
        return false;   
    }
    if (x == 1)
    {
        return false;
    }
    for (int i = 2; i < x; i++)
    {
        if (x % i == 0) 
        {
            return false;
        }
    }
    return true;        
} 

int main()
{
    int a, b;
    cin >> a >> b;
    for (int i = a; i <= b; i++)
    {
        if (is_prime(i))
        {
            if (is_palindrome(i))
            {
                cout << i << endl;  
            }   
        }
    }
    return 0;
} 

by Leo_Longlong @ 2023-08-15 11:32:32

在你原本的dislocation函数中：

    while (y >= 0)
    {
        y /= 10;
        cnt++;
    }

这5行代码会陷入死循环，在新的is_palindrome函数中帮你改了

by littlewhite_ @ 2023-08-15 11:35:40

@Leo_Longlong 不用，在等回复时我已经发现了，不过还是谢谢提醒。

by Leo_Longlong @ 2023-08-15 11:41:47

还有，你本身的is_palindrome函数就有问题，帮你改了（顺带还优化了一下这个函数的时间复杂度）

bool is_palindrome(int n) {
    int reverse = 0;
    while (n > reverse) {
        reverse = reverse * 10 + n % 10;
        n /= 10;
    }
    return n == reverse || n == reverse / 10;
}

by Leo_Longlong @ 2023-08-15 11:43:03

完整代码：

#include <bits/stdc++.h>
using namespace std;

bool is_palindrome(int n) {
    int reverse = 0;
    while (n > reverse) {
        reverse = reverse * 10 + n % 10;
        n /= 10;
    }
    return n == reverse || n == reverse / 10;
}

bool is_prime(int x) {
    for (int i = 2; i < x; i++) {
        if (!(x % i)) {
            return 0;
        }
    }
    return 1;
}

int a, b;

int main() {
    cin >> a >> b;
    for (int i = a; i <= b; i++) {
        if (is_palindrome(i)) {
            if (is_prime(i)) {
                cout << i << '\n';
            }
        }
    }
    return 0;
}

应该能过2/3的数据，66分

by Leo_Longlong @ 2023-08-15 11:50:53

@littewhite

1.对于大于4的数，只有奇数可能是质数，所以时间一下就可以缩短一半。

2.判断素数时，只需要判到i=sqrt(x)时就可以停止了，时间复杂度又会小很多。

ACcode：

#include<bits/stdc++.h>
using namespace std;

bool is_palindrome(int n) {
    int reverse = 0;
    while (n > reverse) {
        reverse = reverse * 10 + n % 10;
        n /= 10;
    }
    return n == reverse || n == reverse / 10;
}

bool is_prime(int x) {
    int sq_x=sqrt(x);
    for (int i = 2; i <= sq_x; i++) {
        if (!(x % i)) {
            return 0;
        }
    }
    return 1;
}

int a, b;

int main() {
    cin >> a >> b;
    if (!(a % 2)) {
        a++;
    }
    for (int i = a; i <= b; i += 2) {
        if (is_palindrome(i)) {
            if (is_prime(i)) {
                cout << i << '\n';
            }
        }
    }
    return 0;
}

by littlewhite_ @ 2023-08-15 11:56:19

@Leo_Longlong 原来如此！非常感谢！

by Leo_Longlong @ 2023-08-15 12:03:22

@littewhite 没事