欧拉筛, 为啥最后一个还通不过

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

un_dauant @ 2023-02-08 21:04:51

#include <algorithm>
#include<bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e8+10;
int prime[maxn];
bool vis[maxn];      //0表示是素数,1表示是合数

void ola(int n){

    int cnt = 0;
    for(int i = 2 ;i <= n;i++){
        if(!vis[i]){
            prime[cnt++] = i;
        }
        //欧拉筛的本质是将所有已经记录的质数的i倍给筛掉
        for(int j = 0 ; j < cnt && i * prime[j] <= n ;j++){
            vis[i*prime[j]] = true;
            if(i % prime[j] == 0) break; //保证每个质数只筛一次
        }
    }
}
bool JudgeIsC(int n){
    int len = 0;
    int a[8];
    while(n!=0){
        a[len++] = n%10;
        n/=10;
    }
    for(int i = 0; i< len/2 ;i++){
        if(a[i] != a[len-i-1]) return false;
    }
    return true;
}
int main()
{
    int a , b;
    scanf("%d%d",&a,&b);
    memset(vis,false,sizeof(bool)*b);
    ola(b);
    for(int i = a;i <= b ;i++){
        if(!vis[i] && JudgeIsC(i)){
            printf("%d\n",i);
        }
    }
    return 0;
}

by olegekei @ 2023-02-08 21:12:50

@un_dauant

if(b>1e7)b=1e7;


by un_dauant @ 2023-02-08 21:43:06

@olegekei 谢谢啦


|