Question

求c语言程序 求1000以内的素数

Answer 1

可以编写一个素数考察函数，在主函数中调用该函数对1000以内的整数穷举考察求解，也可以在主函数中直接对1000以内的整数穷举考察求解。这里提供一个用筛选法求解的代码，思路是声明一个大于等于1000个元素的char型(int型当然也可以，这里只是为了减少空间开销)数组并全部初始化为1，对下标不是素数的元素清0，最后依次输出不为0元素的下标便是题解。为提高操作效率，用2~33间(33^2>1000了，所以考察已充分了)的素数去除大于这个素数而小于等于1000的不为0的数，能整除的便将这个下标的元素清0。当用小于33的最大素数考察完毕后，依次输出数组中不为0的元素下标即可。代码如下：

#include "stdio.h"
int main(int argc,char *argv[]){
	int i,j;
	char m[1001];//声明char型数组作为筛选对象
	for(m[0]=m[1]=0,i=2;i<=1000;m[i++]=1);//m[0]和m[1]赋0,其余赋1备选
	i=2;//考察次数2~33,用期间的素数去除大于i且小于等于1000间不为0的数
	while((j=i)<33){
		while(!m[++j]);//取j为大于i的第一个不为0的数为起始考察对象
		while(j<=1000){
			if(j%i==0)//这个数若能被小于它的素数整除则以它为下标的元素清0
				m[j]=0;
			while(!m[++j]);//下一个不为0的数为考察对象
		}
		while(!m[++i]);//2~33间的下一个素数
	}
	for(j=i=0;i<=1000;i++)//以下是输出
		if(m[i])//不为0的数组元素的下标便是素数
			printf(++j%20 ? "%4d" : "%4d\n",i);//每行输出20个
	if(j%20)
		printf("\n");
	return 0;
}

运行结果如下：

Answer 2

#include "stdio.h"
#include "math.h"
#include "stdlib.h"
int prime(int n)
{
  int i,r;
  int flag=0;
  for(i=2;i<=sqrt(n);i++)
  {
    if( n%i==0)
    {
      flag=1;
      break;
    }
  }
  return flag;
}
int main()
{
  int n,k;
  for(n=2;n<=1000;n++)
  {
    k=prime(n);
    if(k==0)
      printf("%5d",n);
  }
  return 0;
}