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

本文主要是介绍c、c++关于质数||素数的求法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我们要求某个范围内的所有质数，当然最基本最重要的方法就是除一个数取余数在判断是否为0

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

#include<iostream>
#include<math.h>
#include<time.h>#define max 100using 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 100using 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 10000000using 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 100000000using 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");
}

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

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