#8 #10 TLE求优化

IeoA @ 2023-07-18 10:21:59

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

int L, R;

bool range(int x) {
    return !(12 <= x && x <= 99) || (1000 <= x && x <= 9999) || (100000 <= x && x <= 999999);
}

bool palindrome(int x) {
    string str, rstr;
    str = to_string(x), rstr = str;
    reverse(rstr.begin(), rstr.end());
    return rstr == str;
}

bool prime(int x) {
    for (register int i = 3; i <= sqrt(x); ++i, ++i) {
        if (x % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    scanf("%d %d", &L, &R);
    if (L % 2 == 0) {
        L++;
    }
    R = min(9989899, R);
    for (register int i = L; i <= R; ++i, ++i) {
        if (range(i) && palindrome(i) && prime(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

by myworldzycpc @ 2023-07-18 11:38:33

To optimize the given code for finding palindrome prime numbers within a given range, we can improve the efficiency of the palindrome check and prime check functions. Additionally, the current implementation skips even numbers while iterating, which is unnecessary. Let's make the following improvements:

1. Optimize palindrome check: The current implementation converts the number to a string and then checks for palindrome. Instead, we can use an integer-based approach to check if the number is a palindrome.

2. Optimize prime check: The current prime check implementation has a time complexity of O(sqrt(N)). We can use the fact that all prime numbers (except 2 and 3) are of the form 6k ± 1, where k is a positive integer. This will reduce the number of iterations required to check for prime numbers.

Here's the optimized code:

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

int L, R;

bool isPalindrome(int x) {
    int num = x, reversed = 0;
    while (num > 0) {
        reversed = reversed * 10 + (num % 10);
        num /= 10;
    }
    return x == reversed;
}

bool isPrime(int x) {
    if (x <= 1)
        return false;
    if (x <= 3)
        return true;
    if (x % 2 == 0 || x % 3 == 0)
        return false;

    for (int i = 5; i * i <= x; i += 6) {
        if (x % i == 0 || x % (i + 2) == 0)
            return false;
    }
    return true;
}

int main() {
    scanf("%d %d", &L, &R);
    L = max(3, L);
    R = min(9989899, R);

    for (int i = L; i <= R; ++i) {
        if (isPalindrome(i) && isPrime(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

Changes made:

1. The range function is no longer needed as the L and R values are already checked before entering the loop.
2. The even number check for L is no longer necessary as we start the iteration from a valid odd number.
3. The palindrome check now uses integer-based reverse logic instead of converting to a string.
4. The prime check now follows the 6k ± 1 optimization to reduce the number of iterations.

by myworldzycpc @ 2023-07-18 11:40:28

为了优化给定的代码以查找给定范围内的回文素数，我们可以改进回文检查和素数检查函数的效率。此外，当前实现在迭代时跳过了偶数，这是不必要的。让我们进行以下优化：

1. 优化回文检查： 当前实现将数字转换为字符串，然后检查是否为回文。相反，我们可以使用基于整数的方法来检查数字是否为回文。

2. 优化素数检查： 当前的素数检查实现的时间复杂度为O(sqrt(N))。我们可以利用这样一个事实：除了2和3以外的所有素数都是6k ± 1的形式，其中k是正整数。这将减少检查素数所需的迭代次数。

以下是优化后的代码：

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

int L, R;

bool isPalindrome(int x) {
    int num = x, reversed = 0;
    while (num > 0) {
        reversed = reversed * 10 + (num % 10);
        num /= 10;
    }
    return x == reversed;
}

bool isPrime(int x) {
    if (x <= 1)
        return false;
    if (x <= 3)
        return true;
    if (x % 2 == 0 || x % 3 == 0)
        return false;

    for (int i = 5; i * i <= x; i += 6) {
        if (x % i == 0 || x % (i + 2) == 0)
            return false;
    }
    return true;
}

int main() {
    scanf("%d %d", &L, &R);
    L = max(3, L);
    R = min(9989899, R);

    for (int i = L; i <= R; ++i) {
        if (isPalindrome(i) && isPrime(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

做出的改变：

1. range函数不再需要，因为L和R的值在进入循环之前已经被检查过了。
2. 对于L的偶数检查现在不再需要，因为我们从一个有效的奇数开始迭代。
3. 回文检查现在使用基于整数的反转逻辑，而不是转换为字符串。
4. 素数检查现在遵循6k ± 1的优化方法，以减少迭代次数。