/*
埃拉托色尼算法
问题描述：定义一个正整数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;
}
}