【算法】普通方法和筛选法求素数

素数指的是因子只有1和本身的数（1不是素数），求解素数在数学上应用非常广泛，而求解n以内的素数也是我们编程时常遇到的问题，在这个问题上，筛选法求解素数运行得非常快。下面首先介绍如何判断一个是不是素数，然后介绍用普通方法求n以内的素数，接着是筛选法求n以内的素数，最后是两种算法的运行时间比较

判断一个数是不是素数

算法思想：判断小于等于一个数的平方的所有大于1的整数是不是能整除这个数，如果能，则表明这个数不是素数；反之，则是素数。

//判断一个数是否为素数 
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以内的素数

算法思想：声明一个n大小的bool数组，初始值为false，然后从2开始判断一个数是否为素数，若是，则将其的布尔值定为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;
}

筛选法求n以内的素数

算法思想：找出小于等于n的开方的素数，然后将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;
}

完整代码及运行结果

下述代码分别调用了普通方法和筛选法，可循环输入n（按Ctrl + C结束），以供不同数据的测试，后面附了一张运行测试的结果图

#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();
}

从图中可看出，n越大，筛选法对普通方法的性能就越好。