按照《算法分析与设计》里的思路：
1.
// 输出 100 以内的素数
#include<iostream>
#include<math.h>
using namespace std;
const int NUM
= 101;
= 101;
int main(int argc,char *argv[])
{
int prime[NUM];
int i(0),j(0);
for(;i!=NUM;++i)prime[i]
= i;
= i;
for(i
= 2;i <= sqrt(NUM);++i){
= 2;i <= sqrt(NUM);++i){
if(prime[i]
== 0)continue ;
== 0)continue ;
for(j
= i*i;j < NUM;j += i)
= i*i;j < NUM;j += i)
prime[j] = 0;
}
for(i=2;i!=NUM;++i)
if(prime[i]!=0)cout<<prime[i]<<endl;
getchar();
return 0;
}
2.
修改后，得到一个区间的素数
// 输出 low 到 high 之间的素数
#include<iostream>
#include<math.h>
using namespace std;
int main(int argc,char *argv[])
{
int low,high;
cout<< "input your numbers
like: 1 100" <<endl;
like: 1 100" <<endl;
cin>>low>>high;
if(low
< 2 || low >= high){
< 2 || low >= high){
cout<< "input
error!"<<endl;
error!"<<endl;
getchar();
return -1;
}
// 动态数组，初始化
int *prime
= new int[high
- low + 1];
= new int[high
- low + 1];
int i;
for(i
= 0;i != high - low + 1;++i)
= 0;i != high - low + 1;++i)
prime[i] = low + i;
for(i
= 2;i <= sqrt(high);++i){ // 外层
= 2;i <= sqrt(high);++i){ // 外层
if(i*i
<= sqrt(low)){ // i <= 小数的平方根
<= sqrt(low)){ // i <= 小数的平方根
int j
= 0;
= 0;
while(prime[j]
% i != 0)++j; // 寻找第一个能被整除的值
% i != 0)++j; // 寻找第一个能被整除的值
for(;j
< high - low + 1;j += i)
< high - low + 1;j += i)
prime[j] = 0;
}
else{
// i > 小数的平方根，直接找到数值为 i*i 的下标，即 i*i - m
// i > 小数的平方根，直接找到数值为 i*i 的下标，即 i*i - m
int j
= i*i - low;
= i*i - low;
for(;j
< high - low + 1;j += i)
< high - low + 1;j += i)
prime[j] = 0;
}
}
for(i
= 0;i != high - low + 1;++i)
= 0;i != high - low + 1;++i)
if(prime[i]
!= 0)cout<<prime[i]<<endl;
!= 0)cout<<prime[i]<<endl;
delete[] prime;
getchar();
getchar();
return 0;
}