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;
}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
原文：http://blog.csdn.net/s634772208/article/details/46327281
