c、c++关于质数||素数的求法

  • Post author:
  • Post category:其他


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

除一个数取余数在判断是否为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



版权声明:本文为summer_awn原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。