#9 TLE, 求助大佬优化, 已用埃式筛,并且判断了位数

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

MichaelQiu @ 2023-08-24 15:29:56

自己的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]);
}

by MichaelQiu @ 2023-08-24 15:42:15

对不起这个好像是欧拉筛?


by Imerance1018 @ 2023-08-24 16:16:06

_埃氏筛会超_


by B612Dusk @ 2023-08-24 18:40:12

@MikePP 哥们,你的欧拉筛 break 都没有, 这是埃筛,欧拉筛是一路筛出来素数的。

int prime[N], vis[N];
void euler(int x)
{
    m = 0;
    for(reg int i = 2;i <= n;i = -~i)
    {
        if(!vis[i]) prime[cnt ++] = i, m = -~m;
        for(reg int j = 0; prime[j] <= n / i;j = -~j)
        {
            vis[prime[j] * i] = 1; 
            if(i % prime[j] == 0)   break;
        }
    }
}

这个是欧拉筛


by MichaelQiu @ 2023-08-24 18:47:15

@B612Dusk 谢谢dalao知道了(埃筛和欧拉筛是做这题现查的所以不太清楚,但是谢谢啦


by B612Dusk @ 2023-08-24 19:42:23

@MikePP 嘎,好礼貌,我只是路过的蒟蒻


by MichaelQiu @ 2023-08-25 09:06:22

@B612Dusk 哈哈谢谢现在已经全AC啦?


|