超时最后一个点,差一点就AC了!求助!
查看原帖
超时最后一个点,差一点就AC了!求助!
593753
LukeSu楼主2022/5/2 20:32
#include<bits/stdc++.h>
using namespace std;

bool st[111111111], hashtable[111111111];

void Eratosthenes(int u){    //埃拉筛建一个素数表
	for(int i = 2; i <= u; i++){
		if(!st[i]){
			hashtable[i] = true;
			for(int j = i; j <= u; j += i) st[j] = true;
		}
	}  
}	
	
bool isPalindrome(int u){   //判断是否回文
	string s = to_string(u);
	string t(s.rbegin(), s.rend());   //逆序字符串
	if(s == t) return true; //逆序的字符串与原来一样就是对的
	else return false;
}

bool ws(int u){  //回文数,除了11,数字位数为偶数的数定不是素数
	if(u >= 1000 and u < 10000)	return false;	
	if(u >= 100000 and u < 1000000) return false;
	if(u >= 10000000 and u < 100000000) return false;
	return true;
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
	int a, b;
	cin >> a >> b;
	if(a % 2 == 0) ++a; //各位为偶数必不是素数
	Eratosthenes(b);
	for(int i = a; i <= b; i += 2){
		if(ws(i) == false) continue; 
		if(hashtable[i] and isPalindrome(i)) cout << i << endl;
	}
	
	return 0;
}
2022/5/2 20:32
加载中...