## 判断一个数是不是素数

//判断一个数是否为素数
bool isPlain(int value){
int m = sqrt(value);
if (value < 2) return false;
for (int i = 2; i <= m; i++){
if ((value%i)==0){
return false;
}
}
return true;
}


## 普通方法求解n以内的素数

//普通法求素数
bool* putong(int n){
bool* value = new bool[n];
for (int i = 0; i < n; i++)
value[i] = false;
for (int i = 2; i < n; i++){
if (isPlain(i)){
value[i] = true;
}
}
return value;
}


## 筛选法求n以内的素数

//筛选法求素数
bool* shuaixuan(int n){
bool* value = new bool[n];
for (int i = 0; i<n; i++)
value[i] = true;

value[0] = false;
value[1] = false;

for (int i = 2; i <= sqrt(n); i++){
if (value[i] && isPlain(i)){
int c = 2;
int j = i*c;
while (j < n){
value[j] = false;
j = i*c++;
}
}
}
return value;
}


## 完整代码及运行结果

#include <iostream>
using namespace std;
#include <ctime>
#include <math.h>
#include <conio.h>
//判断一个数是否为素数
bool isPlain(int value){
int m = sqrt(value);
if (value < 2) return false;
for (int i = 2; i <= m; i++){
if ((value%i)==0){
return false;
}
}
return true;
}

//普通法求素数
bool* putong(int n){
bool* value = new bool[n];
for (int i = 0; i < n; i++)
value[i] = false;
for (int i = 2; i < n; i++){
if (isPlain(i)){
value[i] = true;
}
}
return value;
}

//筛选法求素数
bool* shuaixuan(int n){
bool* value = new bool[n];
for (int i = 0; i<n; i++)
value[i] = true;

value[0] = false;
value[1] = false;

for (int i = 2; i <= sqrt(n); i++){
if (value[i] && isPlain(i)){
int c = 2;
int j = i*c;
while (j < n){
value[j] = false;
j = i*c++;
}
}
}
return value;
}

int main(){

int n;
while (cin >> n){

int start = clock();
bool* value1 = putong(n);
int end = clock();
cout << "普通方法：" << end - start << endl;

start = clock();
bool* value2 = shuaixuan(n);
end = clock();
cout << "筛选法：" << end - start << endl;

delete[] value1;
value1 = NULL;
delete[] value2;
value2 = NULL;
}
_getch();
}