最后一个超时求助大佬

Catlz @ 2023-12-21 19:43:56

int ZS(int a)
{
    for (int i = 2; i <= sqrt(a); i++)
        if (a % i == 0)return 0;
    return 1;
}
int HW(int a)
{
    stringstream s;
    s << a;
    string temp = s.str();
    for (int i = 0, j = temp.size() - 1; i<j; i++, j--)
    {
        if (temp[i] != temp[j])return 0;
    }
    s.str("");
    s.clear();
    return 1;
}
int main()
{
    int x, y;
    cin >> x >> y;
    for (int i = x; i <= y;)
    {
        if (HW(i))
        {
            if (ZS(i))
                cout << i << endl;
        }
        if (i == x && x % 2 == 0)
        {
            i++; continue;
        }
        i += 2;
    }
    return 0;
}

by wangjiawen @ 2023-12-21 19:48:03

你这个6

这是我第一次见判断素数不优化的

//普通优化，这是最正常的
bool prime(long long x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
        if(x%i==0)
            return 0;
    return 1;
}

//优化的神奇的判素数暴力
bool prime(long long x)
{
    if(x<2)
        return 0;
    if(x<4)
        return 1;
    if(x%6!=1&&x%6!=5)
        return 0; 
    for(int i=5,limit=sqrt(x);i<=limit;i+=6)
        if(!(x%i)||!(x%(i+2)))
            return 0;
    return 1;
}

by wangjiawen @ 2023-12-21 19:48:12

@Ding_dang_mao

by Catlz @ 2023-12-21 19:51:50

@wangjiawen 感谢大佬我试试

by Catlz @ 2023-12-21 19:55:53

@wangjiawen 貌似不是素数判断的原因啊，是这类型转换太浪费了码,我改个

by InversionShadow @ 2023-12-21 19:58:56

i <= min(y, 9989899)

by wangjiawen @ 2023-12-21 19:59:36

你可以试试先构造回文数，在判断素数，因为你这个算法是O(m-n) @Ding_dang_mao

by Catlz @ 2023-12-21 20:02:03

@ydq1101 a啊？大佬威武啊.

by Catlz @ 2023-12-21 20:02:14

@wangjiawen 大佬你的方法我也试试

by wangjiawen @ 2023-12-21 20:05:34

其实这个优化没啥用，才优化了1ms(我应该没算错吧