【USACO】pprime

时间:2021-12-05 22:31:54

开始看第一眼题就觉得问题会在超时上,果然写了个小代码运行到test 9时超时了

#include <stdio.h>
#include <math.h> int isprime(int M)
{
int i;
float N = M;
for(i = ; i <= sqrt(N); i++)
{
if(M % i == )
return ;
}
return ;
} int ispalindromes(int N)
{
char numc[] = {};
int l;
char *p, *q;
for(l = ; N != ; l++)
{
numc[l] = N % + '';
N = N / ;
}
l--;
for(p = numc, q = numc + l; p < q; p++, q--)
{
if(*p != *q)
return ;
}
return ;
} int main()
{
FILE *in, *out;
in = fopen("pprime.in", "r");
out = fopen("pprime.out", "w"); int a, b;
fscanf(in, "%d %d", &a, &b); int i, j;
for(i = a; i <= b; i++)
{
if(ispalindromes(i) && isprime(i))
{
fprintf(out, "%d\n", i);
}
} return ;
}

----------------------------------------------

化简途径是直接生成回文 我的代码边界处理的有点乱 不过AC了 确实速度比一个个判断快很多 大概快个100倍吧

每次回文生成的前半段都是 10 — 99  100 - 999 1000 - 9999 这样的情况,要分奇偶数处理

#include <stdio.h>
#include <math.h> int isprime(int M)
{
int i;
float N = M;
for(i = ; i <= sqrt(N); i++)
{
if(M % i == )
return ;
}
return ;
}
int main()
{
FILE *in, *out;
in = fopen("pprime.in", "r");
out = fopen("pprime.out", "w"); int a, b;
int i, j, k;
int l, s;
int bb, aa;
fscanf(in, "%d %d", &a, &b); bb = b;
aa = a; for(l = ; bb != ; l++)
{
bb = bb / ;
}
for(s = ; aa != ; s++)
{
aa = aa / ;
}
for(i = s; i <= l; i++)
{
int small, large; //回文产生中,不重复部分最大最小值 int ll = i/ + i % ; //回文不重复长度
if(i == s) //最小边界
{
small = a;
for(j = ; j < i - ll; j++)
{
small = small / ;
}
}
else
{
for(small = , j = ; j < ll; j++)
{
small = small * ;
}
}
for(large = , j = ; j <= ll; j++)
{
large = large * ;
}
large--; for(j = small; j <= large; j++)
{
int lll;
int pal;
int num[] = {};
int jj = j;
for(k = ; jj != ; k++)
{
num[k] = jj % ;
jj = jj / ;
}
lll = k;
pal = j;
if(i % == )
{
for(k = ; k < lll; k++)
{
pal = pal * + num[k];
}
if(pal > b) return ; //不能超过最大值
if(isprime(pal))
{
fprintf(out, "%d\n", pal);
} }
else
{
for(k = ; k < lll; k++)
{
pal = pal * + num[k];
}
if(pal > b) return ;
if(isprime(pal))
{
fprintf(out, "%d\n", pal);
}
}
}
} return ;
}

看了下答案,思路差不多,但是比我的清楚很多。学习到的技巧:

素数判断:

int
isprime(long n)
{
long i; if(n == ) // 2单独处理
return ; if(n% == )
return ; for(i=; i*i <= n; i+=) // i * i <= n 可以避免sqrt
if(n%i == )
return ; return ;
}

atol()函数 可以将字符串转为整数