[C++]埃拉托色尼算法

 /*
埃拉托色尼算法 
问题描述:定义一个正整数n,求0-n范围以内的所有质数 
@date 2017-03-06
@author Johnny Zen   
*/ 
#include<iostream>
#include<math.h>
using namespace std;
 
void Eratosthenes(int arrs[],int n){   //arrs暂时设置为空指针,意为在返回目标数组(n范围内的所有质数数组) 
  int sqr,j;
  for(int i=2;i<n;i++){
    arrs[i] = i;     //目标数组初始化 
    sqr = sqrt(i);   //sqr 向下取整   注意:变量名sqr不能取名为sqrt,否则发生关键字冲突,无法编译! 
    for(int k = 2;k<=sqr;k++){   //因为: 在sqrt(i)以后的含小于sqrt(i)倍数关系的数据都已经被清除,剩下的均为质数 
      if(arrs[k]!=0){
        j = pow(k,2);
        while(j<=n){
          arrs[j] = 0;   //因数置0
          j = j+k;       //最为巧妙处: 加法   k*k   k*(k+1)    k*(k+2)  ----k*(k+n) 
        }
      }
    }
  }
  //输出
  for(int i = 2;i<n;i++)
    if(arrs[i]!=0)
      cout<<arrs[i]<<'\t'; 
 
int main(){
  int n,*arrs;
  cout<<"请输入数N:";
  cin>>n;
  arrs = new int[n];  //创建数组 
  
  Eratosthenes(arrs,n);
  
  delete [] arrs; 
  return 0;
上一篇:②jquery复习


下一篇:WPF Get jiayuan outbox list(send mail box)