Question

C语，编一个程序，输出1000以内所有素数。要求：设计一个函数，专门用于判断数值为素数。2 将素数每行8个

格式输出

#include <stdio.h>
int isPrime(int a[]);
void output(int a[]);
#define n 1000
void main()
{
int a[n];
a[n]=isPrime(a);
output(a);
}

int isPrime(int a[n])
{
int i,x;
for(i=2;i<1000;i++){
for(x=2;x<i;i++){
if(i%x==0)
break;
if(i==x)
return a[n];
}
}
}

void output(int a[n])
{
int i;
while(a[n]!='\0'){
for(i=1;i<=n;i++){
if(i%8==0)
printf("\n");
else
printf("%4d",&a[i]);
}
}
}

求高手看看哪错了

Answer 1

：改进后的程序效率大为提高判断997是素数只要循环到31即可结束，判断1000不是素数只要循环到2即可结束。同时不再需要使用数组。包含math.h是为了计算平方根。

#include <stdio.h>

#include <math.h>

int isPrime(int a);

void output(int a);

#define n 1000

void main()

{

int i,k=0;

for(i=2;i<=n;i++)

{

 if(isPrime(i))

 {

   printf("%4d",i);

   if(++k%8==0)

     printf("\n");

 }

}

printf("\n");

}

int isPrime(int a)

{

int i,x;

for(i=2;i<=sqrt(a);i++)        /*改进后的函数效率大为提高*/

 if(a%i==0)return(0);

return 1;

}

追问

两个问题：1.为什么求素数跟平方根有关系
2.int a被定义后并未说明大小，为什么后面可以直接使，（i<=sqrt(a))，那么a到底是从几开始的呢？又到几截止，不太明白

追答

1. 为了减少判断次数。以997为例，根号997=31.6，只要从2到31不能整除997，就能判定997是一个素数。如999不是素数，它肯定有一个因子小于根号999。

2. int a被定义后并未说明大小，它在被调用时从形式参数中获得值（例如调用isprime(997)时，a的值就是997）。循环变量是i，它从2开始，一直到根号a为止。