/*

埃拉托色尼算法 

问题描述：定义一个正整数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;
}