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啦?