博客

我们要求某个范围内的所有质数，当然最基本最重要的方法就是

除一个数取余数在判断是否为0

一、最简单的粗暴的穷举法

#include<iostream>
#include<math.h>
#include<time.h>

#define max 100

using namespace std;

void main() {

	clock_t start, end;

	start = clock();

	int * prime = (int*)malloc(sizeof(int)*max);//记录所有素数的数组

	int count = 1;//素数的个数

	*prime = 2;//初值

	for (int i = 3; i <= max; ++i) {

		bool choice = true;//假设为质数

		for (int j = 2; j <i; ++j) {

			if (i%j == 0) {//不是质数

				choice = false;

				break;
			}
		}

		if (choice) {

			*(prime + count) = i;

			count++;
		}
	}
	free(prime);//释放素数的数组指针，避免内存泄漏

	end = clock();

	float time = (float)(end - start) / 1000;

	cout << "time is  " << time << "s" << endl;

	cout << "count is  " << count << endl;

	system("pause");
}

二、循环范围由2~i-1变成2~sqrt（i）

至于为什么是sqrt（i）自己思考吧，数学问题

#include<iostream>
#include<math.h>
#include<time.h>

#define max 100

using namespace std;

void main() {

	clock_t start, end;

	start = clock();

	int * prime = (int*)malloc(sizeof(int)*max);//记录所有素数的数组

	int count = 1;//素数的个数

	*prime = 2;//初值

	for (int i = 3; i <= max; ++i) {

		bool choice = true;//假设为质数

		for (int j = 2; j <=sqrt(i); ++j) {

			if (i%j == 0) {//不是质数

				choice = false;

				break;
			}
		}

		if (choice) {

			*(prime + count) = i;

			count++;
		}
	}

	for (int i = 0; i < count; ++i) {
		cout << prime[i] << endl;
	}

	free(prime);//释放素数的数组指针，避免内存泄漏

	end = clock();

	

	float time = (float)(end - start) / 1000;

	cout << "time is  " << time << "s" << endl;

	cout << "count is  " << count << endl;

	system("pause");
}

三、我们发现每次循环都调用sqrt函数比较慢，所以先把这个数赋给k，直接调用k就好了

#include<iostream>
#include<math.h>
#include<time.h>

#define max 10000000

using namespace std;

void main() {

	clock_t start, end;

	start = clock();
		
	int * prime = (int*)malloc(sizeof(int)*max);//记录所有素数的数组

	int count = 1;//素数的个数

	*prime = 2;//初值

	for (int i = 3; i <= max; ++i) {

		bool choice = true;//假设为质数

		int k = sqrt(i);

		for (int j = 2; j <= k ; ++j) {

			if (i%j == 0) {//不是质数

				choice = false;

				break;
			}
		}

		if (choice) {

			*(prime + count) = i;

			count++;
		}
	}
	free(prime);//释放素数的数组指针，避免内存泄漏

	end = clock();

	float time = (float)(end - start)/1000;

	cout << "time is  " << time <<"s"<< endl;

	cout << "count is  " << count << endl;

	system("pause");
}

四、这步优化相对困难。我们知道，所有合数都能写成若干素数相乘的形式，故判断i数i是否为质数，只需要用i除以从2到sqrt（i）之间的质数就可以，不需要除以这个区间的合数。但是问题出现了，我们要记录所有小于i的质数，这就要用堆内存建立一个整型数组，数组长度为max（我在考虑是不是可以建一个更小点的，，，算了，比较懒，不想了）用来保存所有已经求过的质数，这步的关键还有就是默认好2是第一个质数。

#include<iostream>
#include<math.h>
#include<time.h>


#define max 100000000


using namespace std;


void main() {


	clock_t start, end;


	start = clock();


	int * prime =(int*) malloc(sizeof(int)*max);//记录所有素数的数组


	int count = 1;//素数的个数


	*prime = 2;//初值


	int tempmax = 0;//小于sqrt（i）的最大素数下标


	for (int i = 3; i <= max; ++i) {


		bool choice = true;//假设为质数


		int k = sqrt(i) + 1;


		for (int j = 0; j <=tempmax; ++j) {


			if(prime[tempmax] < k)tempmax++;


			if (i % prime[j] == 0) {//不是质数


				choice = false;


				break;
			}
		}


		if (choice) {//是质数


			*(prime + count) = i;


			count++;
		}
	}
	//for (int i = 0; i < count; ++i) {
	//	cout << i<<"            "<<prime[i] << endl;
	//}
	free(prime);//释放素数的数组指针，避免内存泄漏


	end = clock();


	float time = (float)(end - start) / 1000;
	
	cout << "time is  " << time << "s" << endl;


	cout << "count is  " << count << endl;


	system("pause");
}	clock_t start, end;


	start = clock();


	int * prime =(int*) malloc(sizeof(int)*max);//记录所有素数的数组


	int count = 1;//素数的个数


	*prime = 2;//初值


	int tempmax = 0;//小于sqrt（i）的最大素数下标


	for (int i = 3; i <= max; ++i) {


		bool choice = true;//假设为质数


		int k = sqrt(i) + 1;


		for (int j = 0; j <=tempmax; ++j) {


			if(prime[tempmax] < k)tempmax++;


			if (i % prime[j] == 0) {//不是质数


				choice = false;


				break;
			}
		}


		if (choice) {//是质数


			*(prime + count) = i;


			count++;
		}
	}
	//for (int i = 0; i < count; ++i) {
	//	cout << i<<"            "<<prime[i] << endl;
	//}
	free(prime);//释放素数的数组指针，避免内存泄漏


	end = clock();


	float time = (float)(end - start) / 1000;
	
	cout << "time is  " << time << "s" << endl;


	cout << "count is  " << count << endl;


	system("pause");
}

这点东西做了一上午，哎，真是咸鱼。。。大二重新做人吧

关于速度的结果如下，可以看到每一步的优化是有效果的，而且在求较大范围的质数时更加明显

本文章可能存在很多不足，请多指点

2017 / 7 / 7