#9 TLE, 求助大佬优化, 已用埃式筛,并且判断了位数
查看原帖
#9 TLE, 求助大佬优化, 已用埃式筛,并且判断了位数
1050603
MichaelQiu楼主2023/8/24 15:29

自己的MacBook上输入5, 100000000编译时间只有0.5s, 但是输到评测机并在开O2的情况下最后一个点成功TLE了, 求助大佬 orz

#include <cstdio>
#include <cmath>

const unsigned int PRIME_MAX = 100000009;

unsigned int primes[PRIME_MAX];
bool isComp[PRIME_MAX]; // 记录合数,默认均为素数

// 判断回文
bool isPalindrome(unsigned int num)
{
    unsigned int tmp = num, mun = 0;
    while (tmp)
    {
        mun = mun*10 + tmp%10;
        tmp /= 10;
    }
    
    if (num == mun) return true;
    else return false;
}

int main()
{
    unsigned int n, m, cnt=0;
    std::scanf("%d%d", &n, &m);
    
    // 埃式筛
    for (unsigned int i=2; i<=m; i++)
    {
        if (!isComp[i]) // 素数
        {
            int digit = log10(i) + 1; // 位数
            if (i >= n && isPalindrome(i) && ( (i==11) ^ (digit%2) ))
                primes[cnt++] = i; // 记录素数
            for (unsigned int j=i*2; j<=m; j+=i)
                isComp[j] = true; // 均为合数,下次不再判断
        }
    }
    
    for (int i=0; i<cnt; i++)
        std::printf("%d\n", primes[i]);
}
2023/8/24 15:29
加载中...