一、素数的定义
质数又称素数。指在一个大于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 }。
定义一个全局变量和一个全局数组，要是数组是分配在栈上的话，是有容量限制的。所以我们就定义个全局的。
分析：该算法的时间复杂度为O（n*sqrt(n) )，在n比較大时（比方n = 50000），我的机器跑了个二十来秒。就也叫算法。呵呵，所以接下来我们来看还有一种算法 ，那就是古希腊数学家的埃拉托色尼给出的一个比較省力的算法------埃拉托色尼筛法。
2、算法二：筛选法
首先，列出从2開始的数。然后，将2记在素数列表上，再划去全部2的倍数。
三、两种算法的执行时间对照
质数又称素数。指在一个大于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万以内的素数执行时间对照
四、空间上的优化
略
作者：山丘儿
转载请标明出处，谢谢。原文地址：http://blog.csdn.net/s634772208/article/details/46327281