boolisPalindrome(int x){ int a[15] = {0}; int flag = 0; while(x > 0){ a[flag] = x % 10; x /= 10; flag++; } for(int i = 0; i < flag / 2; i++){ if(a[i] != a[flag - i - 1]) returnfalse; } returntrue; }
boolisPrime(int x){ if(x < 2) returnfalse; for(int i = 2; i <= sqrt(x); i++){ if(x % i == 0) returnfalse; } returntrue; }
boolisValidRange(int x){ if((1000 <= x && x <= 9999) || (100000 <= x && x <= 999999)) returnfalse; returntrue; }
intmain(){ int l, r; cin >> l >> r; if(l == 2) cout << "2" << endl; if(l % 2 == 0) l++; r = min(9999999, r); for(int i = l; i <= r; i += 2){ if(!isValidRange(i)) continue; if(!isPalindrome(i)) continue; if(!isPrime(i)) continue; cout << i << endl; } return0; }
核心原理:对于每个合数,都只由它最小的质因子筛掉。 比如:(假定:ans[]数组中存放着已经确定的素数)合数 i = p(最小素因子)* a; 若 i%ans[j] ==0; 则 i * ans[j+1] = p * a * ans[j+1] 可以被后面的 a * ans[j+1] 再乘以素数 p 筛选出来, (显而p<ans[j+1]所以i%ans[j] == 0 时要停止)