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

我们要求某个范围内的所有质数，当然最基本最重要的方法就是除一个数取余数在判断是否为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