文本文档 (2).txt

Erathosthenes给一个自然数a

Erathosthenes算法的实现   
  /*   vc++6.0   &   win2000server   下调试通过   */   
  /***************************************   
    int   test(int   a)   
    功能：给一个自然数a，判断是否为质数。   
    返回值：是质数返回1；反之，返回0   
    算法解释：因为，如果a是素数，那么它不会被2~sqrt(a)之间所有的素数整除。   
    所以在程序中只用比sqrt(a)小的质数去测试a，进一步提高了效率。   
    部分变量说明：int   *p－－存放比sqrt(a)小的质数的数组的指针。   
                                int   flag－－标志信号，用于跳出循环。   
        long   length－－准备存放比sqrt(a)小的质数空间的长度（有   
        一点余度）   
  ***************************************/   
  #include<iostream.h>   
  #include<math.h>   
  #include<malloc.h>   
    
  int   test(long   a)   
  {   
  long   i,j,k=0;//i,j临时变量；k计数   
  long   length;   
  int   *p;   
  int   flag=0;   
  length=(int)sqrt(a);//计算存放比sqrt(a)小的质数空间的大小   
  p=(int*)malloc(length*sizeof(int));//分配空间   
          p[0]=2;//赋初值   
  if(a==1)return   0;//边界处理   
          for(i=2;i<=sqrt(a);i+=2)//除了2的偶数一定不是质数，所以每次＋2     
  {     
  for(j=0;j<=k;j++)//把每一个比sqrt(a)小的质数用来测试   
  {   
  if(a%p[k]==0)//表示a不是质数   
  {   
  flag=1;//做标记   
  break;//跳出该循环   
  }   
  if(i%p[k]==0)   break;//同时测试i是否为质数   
  }   
  if(flag==1)break;   
                  if(j>k)//表示i是质数   
  {   
  k++;//数组指针往后移一位   
  p[k]=i;//把刚得到的质数存放起来   
  }     
  }   
          if   (i>sqrt(a))   return   1;//每个循环都做完了才可能i>sqrt(a)，即：   
                                                  //没有一个比sqrt(a)小的质数能整除a，   
                                                  //等价于：a是质数   
          else   return   0;//反之：a不是质数   
  }   
  /*********************************   
  int   main()   
  功能：用于测试test()函数的主程序   
  返回值：正常推出返回0   
  输入：按提示输入一个自然数   
  输出：输入的自然数是否为质数   
  *************************************/   
  int   main()   
  {   
  long   input;   
  cout<<"请输入一个自然数"<<endl;   
  cin>>input;   
  if(test(input))   
  {   
  cout<<input<<"   is   a   Prime"<<endl;   
  }   
  else   
  {   
  cout<<input<<"   is   not   a   Prime"<<endl;   
  }   
  return   0;   
  }