求助,打表全超内存

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

hailong126 @ 2022-09-08 20:59:46

#include<stdio.h>
#include<bits/stdc++.h>
const int MAXN = 100000001; 
int prime[MAXN];
void Prime()  
{  
    for (int i=0; i<MAXN; i++) prime[i]=1;
    prime[0]=prime[1]=0;  
    for (int i=2; i<MAXN; i++)  
    {  
        if (!prime[i]) continue;  
        for (int j=i*2; j<MAXN; j+=i)
            prime[j] = 0;
    }  
}

int main(){
    int a,b;
    Prime();
    scanf("%d%d",&a,&b);
    int data=0;
    int dao=0;
    for(int i=a;i<=b;i++){
        if(i<10){
            if(prime[i]) printf("%d\n",i);
        }else{
            data=i;
            dao=0;
            while(data!=0){
                dao=dao*10+data%10;
                data=data/10;
            }
            if(dao==i && prime[i]){
                printf("%d\n",i);   
            }
        }
    }
    return 0;
}

求助,打表全超内存


by Katz @ 2022-09-08 21:03:17

你开一亿个int不爆才怪


by SamHJD @ 2022-09-08 21:05:41

这暴力, 不RE也得T的很惨...

RE的地方在12行, j+=i的时候一次加大了就会超过maxn


by youdu666 @ 2022-09-08 21:19:29

@hailong126 建议使用分段打表(doge)


by youdu666 @ 2022-09-08 21:20:19

还有,你这个不算打表吧,打表是在本地计算直接给数组赋值……


by hailong126 @ 2022-09-09 08:34:56

@youdu666 懂了,感谢指点!


by hailong126 @ 2022-09-09 08:36:40

@SamHJD 我参考的题解中的‘埃氏筛选法+回文数判断’这篇,我的不知为何就过不了,呜呜呜。。


by youdu666 @ 2022-09-09 19:36:41

@hailong126 试试用一下线性筛,就是对于每一个数都用已经记录过的质数(可以另开一个数组记录)更新出更大的值并标上不是质数,线性筛是严格线性的,1e8应该没什么问题


by hailong126 @ 2022-09-10 09:46:11

好的,谢谢各位友友


by Tintin2011 @ 2022-09-15 17:44:40

us发表过;这暴力太惨了吧


by zlc_521 @ 2022-09-25 17:16:44

偶数位回文一定是质数


| 下一页