这段代码有什么问题吗?

P1217 [USACO1.5] 回文质数 Prime Palindromes

Chinese_Dragon @ 2023-05-17 17:06:05

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,sz[100000],z=0,t,k,xsz[100000],f=0;
    scanf("%d %d",&a,&b);
    for (int j=a;j<=b;(a%2==0)?j++:j+=2)
    {
        t=j;
        k=0;
        while(t!=0) 
        {
            k=k*10+t%10;
            t/=10;
        }
        if (k==j&&j%2==1)
        {
            sz[f]=j;
            f++;
        }
    }
    for (int u=0;u<=f-1;u++)
    {
        for (int i=2;i<=sqrt(sz[u]);i++)
        {
            if (sz[u]%i==0)
            {
                goto here;
            }
        }
        xsz[z]=sz[u];
        z++;
        here:;
    }
    for(int i=0;i<=z-1;i++)
    {
        printf("%d\n",xsz[i]);
    }
    return 0;
}

不开O2就88分(最后一点TLE) 开了就AC……


by SnowTrace @ 2023-05-17 17:14:48

复杂度不对。


by Chinese_Dragon @ 2023-05-17 17:56:14

我才刚学c++半年左右,时间复杂度什么的不知道啊!!!

(我只知道此段代码的复杂度为O(n) ,正确的是O(log n)吧……关键是如何优化呢orz)


by Chinese_Dragon @ 2023-05-17 18:42:45

@Phantom2009 能指点一下么?

(能否说一下具体什么地方能优化?)


by Starry_dream @ 2023-05-25 19:32:31

你什么时候在这了


by Starry_dream @ 2023-05-25 19:34:37

两个循环合并成一个!!!!!!!!


by Starry_dream @ 2023-05-25 19:37:26

我来给你完整代码(抄袭


|