高考问答诺尔德:c高手进 一道ACM的题目(改得好的话再送100分)
来源：百度文库 编辑：高考问答 时间：2024/04/29 10:30:57
输入a 和 b 其中5<=a<b<=100,000,000
Sample Input
5 500
Sample Output
5
7
11
101
131
151
181
191
313
353
373
383
以下为我的程序
#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define LEN sizeof(struct list)
typedef struct list
{long n;
struct list *next;
}L;
long re(long a)
{
long t,b;
b=a;
for(t=0;a>0;a/=10)
t=t*10+a%10;
if(t==b)return 1;
else return 0;
}
main()
{L *p,*head,*r;
long i,is_prime,m,s;
double sqrt_i;
scanf("%ld %ld",&m,&s);
head=r=p=(L*)malloc(LEN);
p->n=2;
for(i=3;i<=s;i++)
{is_prime=1;
sqrt_i=sqrt((double)i);
for(p=head;p->n<=sqrt_i&&is_prime;p=p->next)
if(i%p->n==0)
is_prime=0;
if(is_prime)
{p=r;
p->next=(L*)malloc(LEN);
p=p->next;
r=p;
p->n=i;
p->next=NULL;
}
}
for(p=head;p->n<m;p=p->next)
free(p);
for(;p->n>=m&&p->n<=s&&p!=NULL;p=p->next)
{if(re(p->n))
printf("%ld\n",p->n);
free(p);
}
getch();
}
问题是每次算到3万多就不能算了 且最后会出现Null Pointer Assignment
请高手帮忙
bearscafe:哈 你的想法和我的一样我已经把基本思路写在纸上了 只不过最近要考试没空编程
我就是想看看有没有更好的方法
在 0 和 10^8 之间，素数有 5,761,455 个（http://www.research.att.com/~njas/sequences/table?a=6880&fmt=4），
回文数则有 19,998 个（http://www.research.att.com/~njas/sequences/table?a=50250&fmt=4），
所以应该穷举回文并逐一检测素性。
题目的下限是 5，而大于 2 的素数都是单数，因此在考虑范围内的回文数少了大约一半，
所以我写了如下的程序。 你可以参考参考。
#include <stdio.h>
#include <math.h>
#include <string.h>
int palindromic( unsigned candidate ) {
char a[ 11 ], i, j;
sprintf( a, "%u", candidate );
for ( i = 0, j = strlen( a ) - 1; i < j; i++, j-- )
if ( a[ i ] != a[ j ] )
return 0;
return 1;
}
/* Assumption: 5 <= lower < upper <= 1,000,000,000 */
void printPalindromicPrimes( const unsigned lower, const unsigned upper ) {
unsigned pld = 11 < lower ? lower : 11, /* start loop with 2D numbers */
order = ceil( log10( pld + 1 ) ); /* number of digits */
/* special-case single-digits */
if ( lower <= 5 && 5 <= upper ) puts( "5" );
if ( lower <= 7 && 7 <= upper ) puts( "7" );
/* start palindrome enumeration from the first odd palindrome >= lower */
pld += pld % 2 == 0 ? 1 : 0;
while ( ! palindromic( pld ) )
pld += 2;
while ( pld <= upper ) {
/* Prime? */
unsigned i = 3;
for ( ; i * i <= pld; i += 2 )
if ( pld % i == 0 )
goto skipPrinting;
printf( "%u\n", pld );
skipPrinting:
/* palindromic increment-by-2, i.e. increment of the middle and
* potential outward carry propagation
*/
pld += pow( 10, order / 2 );
/* if got fatter, make it the smallest odd of the new order */
if ( ceil( log10( pld + 1 ) ) > order )
pld = pow( 10, order++ ) + 1;
else
/* increment the right-half, if the order
is even or the middle digit turned 0 */
if ( order % 2 == 0 || pld / ( int ) pow( 10, order / 2 ) % 10 == 0 ) {
short digitIndex = order / 2 - 1,
carry = 1;
for ( ; digitIndex && carry; digitIndex-- )
/* carry if the current digit is 9 */
if ( pld / ( int ) pow( 10, digitIndex ) % 10 == 9 ) {
carry = 1;
pld -= 9 * pow( 10, digitIndex );
}
else {
carry = 0;
pld += pow( 10, digitIndex );
}
pld += carry; /* of LSD */
}
/* increment both MSD and LSD if palindrome turned even */
if ( pld % 2 == 0 )
pld += pow( 10, order - 1 ) + 1;
}
}
int main( ) {
unsigned l, u;
scanf( "%u %u", &l, &u );
printPalindromicPrimes( l, u );
return 0;
}
我用gcc编译了一下，发现你的代码连测试用例（5 500）都通不过。Sample Output为：
5 7 11 101 131 151 181 191 313 353 373 383
但你的输出只有：
5 7 11
我觉得，应该首先构造（注意，是构造，而不是搜索）给定范围内的所有回文数，存在一个表中（不必用链表），然后再逐一判断表中的每个回文数是否为素数。
如果先判素数，再判回文，那计算量就太大了，浪费空间也太大，不可取。
既然你会编程,就给你讲一下我的算法吧!
首先,既然是质数,那么除了2以外都是奇数了!
假设要生成长度为N的素数回文数,
那么第I位和第N+1-I位的数字就是相同的，那么我们只需要枚举最多N DIV 2+1位
因为该数字最大不过100,000,000
9位而已!!!
只需要穷举5(因为个位必为奇数,所以第一位也必须是基数)*10*10*10=5000次!
接着只需要判断是否为质数就可以了!