问题是:给定数N(2<=N<=8),生成所有其前任意位都是质数的N 位质数。7331既是一个四位质数，因为7，73，733页均是质数。在标准输出上按升序输出所有符合要求的质数，例如：N=2，时输出  ： 23 29 31 37 53 59 71 73 79


这个题目我做的时候还是想了有一点时间，开始还想用第归，后来发现用循环也可以完成，最后是做出来了分享一下 ，在运行的时候发现这个程序很耗CPU，我运行时达到了50% 空闲时为10%以下不开其它程序情况下，CORE I5的CPU 。谁也可以测试一下，然后分析一下。下面是原

#include<alloc.h>
#include<stdio.h>
#include<math.h>
int F(long n);
main()
{ long *p,*q,*w;
int i,j,n,m=4,k;
printf("please input a number\n");
scanf("%d",&n);
printf("\n");
p=(long *)realloc(5,sizeof(long));
*p=2;*(p+1)=3;*(p+2)=5;*(p+3)=7;*(p+4)=9;
for(i=1;i<n;i++)
  { q=(long *)realloc(4*m,sizeof(long));
   w=q;
   k=m; m=0;
    for(j=0;j<k;j++)
      { if(F(*p*10+1)) {*q=*p*10+1;q++;m++;}
     if(F(*p*10+3)) {*q=*p*10+3;q++;m++;}
     if(F(*p*10+7)) {*q=*p*10+7;q++;m++;}
    if(F(*p*10+9)) {*q=*p*10+9;q++;m++;}
      p++;
      }
    free(p);
    p=(long *)realloc(m,sizeof(long));
    for(j=0;j<m;j++)
      *(p+j)=*(w+j);
    free(q);
   }
for(i=0;i<m;i++)

 { printf("%d\t",*(p+i));
  if(i%8==0)printf("\n");
  }
free(p);
}
int F(long n)
{int i,flag=1;
for(i=2;i<sqrt(n);i++)
     if(n%i==0){ flag=0;break;}
return flag;
}

代码：

我也写了个，不过跟你的输出结果有点不一样，你看看效率怎么样：

#include <stdio.h>
#include <stdlib.h>

void main()
{
    int n;
    printf("please input a number : 2<=n<=8\n");
    scanf("%d",&n);
    int N = 1;
    int _start, _end;
    while (--n)
    {
        N *= 10;
    }
    _start = N;
    _end = N*10;
    int _middle = (_end>>1);
    int *array = (int *)malloc(_end*sizeof(int));
    int i = 0;
    int j = 2;
    int mul = 0;
    for (; i<_end; i++)
    {
        array[i] = i;
    }
    for (j=2; j<_middle; j++)
    {
        for (i=2; i<_middle; i++)
        {
            if ((mul=j*i)>=_end)
            {
                break;
            }
            array[mul] = 0;
        }
    }
    for (i=_start; i<_end; i++)
    {
        int tmp = i;
        while (tmp!=0)
        {
            if (array[tmp]!=0)
            {
                tmp /= 10;
            }
            else
            {
                break;
            }
        }
        if (tmp==0)
        {
            printf("%d ",i);
        }
    }
    free(array);
}

[ 本帖最后由 demonleer 于 2012-6-7 00:06 编辑 ]

运行实例：
输入2得到：
  我看你的结果里没有11 13 17 19这些 难道这些不符合条件？
输入3：

输入4：


[ 本帖最后由 demonleer 于 2012-6-7 00:05 编辑 ]

1既不是质数，也不是合数

有道理啊， 我咋把这出给忘了，1不是质数~

#include <stdio.h>
#include <stdlib.h>

void main()
{
    int n;
    printf("please input a number : 2<=n<=8\n");
    scanf("%d",&n);
    int N = 1;
    int _start, _end;
    while (--n)
    {
        N *= 10;
    }
    _start = N;
    _end = N*10;
    int _middle = (_end>>1);
    int *array = (int *)malloc(_end*sizeof(int));
    int i = 0;
    int j = 2;
    int mul = 0;
    for (; i<_end; i++)
    {
        array[i] = i;
    }
    for (j=2; j<_middle; j++)
    {
        for (i=2; i<_middle; i++)
        {
            if ((mul=j*i)>=_end)
            {
                break;
            }
            array[mul] = 0;
        }
    }
    array[1] = 0;                           //在2楼的代码中加这样一句就OK了
    for (i=_start; i<_end; i++)
    {
        int tmp = i;
        while (tmp!=0)
        {
            if (array[tmp]!=0)
            {
                tmp /= 10;
            }
            else
            {
                break;
            }
        }
        if (tmp==0)
        {
            printf("%d ",i);
        }
    }
    free(array);
}

联想Y470 core I3 四核处理器 win7家庭普通版 耗时不到1毫秒 瞬时最大CPU占用率5%

还能优化，不过懒得弄了。

#include<stdio.h>
#include<math.h>

int E[9][16], C[9];

int is_prime(int a)
{
    int i, b;
    b = (int)sqrt(a);
    for(i = 3; i <= b && a % i; i += 2);
    return i > b;
}

void init()
{
    int i, j, t;
    E[1][0] = 2;
    E[1][1] = 3;
    E[1][2] = 5;
    E[1][3] = 7;
    C[1] = 4;
    for(i = 2; i < 9; i++)
    for(j = 0; j < C[i - 1]; j++)
    {
        if(is_prime(t = E[i - 1][j] * 10 + 1)) E[i][C[i]++] = t;
        if(is_prime(t += 2)) E[i][C[i]++] = t;
        if(is_prime(t += 4)) E[i][C[i]++] = t;
        if(is_prime(t += 2)) E[i][C[i]++] = t;
    }
}

void print(int n)
{
    int i;
    for(i = 0; i < C[n]; printf("%d ", E[n][i++]));
    puts("");
}

int main()
{
    int i;
    init();
    for(i = 2; i <= 8; print(i++)) printf("%d : ", i);
    return 0;
}

果然用到平方根了 一时没想起来 我就用了middle了

你用数组，我用动态内存，哪个优化一点？我后来又测了一下，CPU占用不高，原来的测试有误。可以从运行时间，占内存，来考虑。

膜拜版主