素数算法的优化之路

全栈程序员-站长 • 2022年6月20日下午10:16 • 未分类 • 阅读 27

大家好，又见面了，我是你们的朋友全栈君。一、素数的定义

  质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数(不包括0)整除的数。因为合数是由若干个质数相乘而得来的，所以，没有质数就没有合数，由此可见质数在数论中有着很重要的地位。

      比如：2，3，5，7，9…..都是素数。

二、构造素数算法

     写算法之前，先来说说以下这个东西：

     对于任意一个合数n，如果它有两个质因子x，y，显然n = x*y，
     所以，由不等式性质可得，x <= sqrt(n)，即 x <= n^(1/2)。

推广一下，对于任意一个合数，如果它有k个质因子x1，x2，x3，…. ，xk，显然n = x1 * x2 * x3 * …. * xk，
所以，由不等式性质可得， x <= n^(1/k)，即每个质因子必小于或者等于n开k次方，其中x 属于集合{
x1，x2，x3，…. ，xk
}。

定义一个全局变量和一个全局数组，要是数组是分配在栈上的话，是有容量限制的，所以我们就定义个全局的。

const unsigned int N = 50000;

bool flag[N+1];

1、算法一：按照定义，即可快速写出一个简单的构造素数算法

void PrimeCreateCommon()//按照定义
{
	for ( unsigned int i = 2; i <= N; ++i )
	{
		//由前面的铺垫，这里不难理解吧。因为我不知道这个数有几个质因子，
		//我就假设它只有两个，范围拉大一些，这个数的所有质因子都小于或
		//等于sqrt( (double)i ) + 1。其它的约数，必然是这些质因子的倍数
		//而已所以就没必要继续除下去了。
		bool flag = true;
		for ( unsigned int j = 2; j <= sqrt((double)i)+1; ++j )  
		{                              
			if ( i % j == 0 )         
			{                        
				flag = false;
			}
		}
		//if ( flag )
		//{
		// 	cout << i << " "; 
		//}
	}
	cout << endl;
}

分析：该算法的时间复杂度为O（n*sqrt(n) )，在n比较大时（比如n = 50000），我的机器跑了个二十来秒，就也叫算法，呵呵，所以接下来我们来看另一种算法，那就是
古希腊数学家的埃拉托色尼给出的一个比较省力的算法——埃拉托色尼筛法。

2、算法二：筛选法

首先，列出从2开始的数。然后，将2记在素数列表上，再划去所有2的倍数。根据定义，剩下的最小的数——在这里是3——必定是素数。将这个数记在素数列表上，再划去所有它的倍数，这样又会剩下一些数，取其中最小的，如此反复操作。最后剩下的都是素数。

void PrimeCreateExt()//筛选法优化
{
	memset( flag, 0, (N+1)*sizeof(bool) );
	for ( unsigned int i = 2; i <= sqrt(double(N)) + 1; ++i )
	{
		if ( !flag[i] )
		{
			for ( unsigned int j = 2*i; j <= N; j += i )
			{
				flag[j] = true;
			}
		}

	}

// 	for ( int i = 2; i <= N; ++i )
// 	{
// 		if ( !flag[i] )
// 		{
// 			cout << i << " ";
// 		}
// 	}
// 	cout << endl;
}

三、两种算法的运行时间对比

//测试函数
int main()
{
	clock_t start, finish;
	double duration = 0.0;

	cout << "筛选算法产生素数：" << endl;
	start = clock();
	PrimeCreateExt();
	finish = clock();
	duration = (double)(finish-start);
	cout << "时间消耗:" << duration << "ms" << endl << endl;

	cout << "普通算法产生素数：" << endl; 
	start = clock();
	PrimeCreateCommon();
	finish = clock();
	duration = (double)(finish-start);
	cout << "时间消耗:" << duration << "ms" << endl << endl; 
}

//产生50万以内的素数运行时间对比

素数算法的优化之路