如下：
[cpp] // 普通的筛素数方法与改进之后的效率对比
// by MoreWindows( http://www.2cto.com )
#include
#include
#include
#include
const int MAXN = 100000000;
bool flag[MAXN];
int primes[MAXN / 3], pi;
// 利用对每个素数的倍数必定不是素数来筛选
void GetPrime_1()
{
int i, j;
pi = 0;
memset(flag, false, sizeof(flag));
for (i = 2; i < MAXN; i++)
if (!flag[i])
{
primes[pi++] = i;
for (j = i; j < MAXN; j += i)
flag[j] = true;
}
}
// 利用了每个合数必有一个最小素因子来筛选
void GetPrime_2()
{
int i, j;
pi = 0;
memset(flag, false, sizeof(flag));
for (i = 2; i < MAXN; i++)
{
if (!flag[i])
primes[pi++] = i;
for (j = 0; (j < pi) && (i * primes[j] < MAXN); j++)
{
flag[i * primes[j]] = true;
if (i % primes[j] == 0)
break;
}
}
}
int main()
{
printf(" 在%d的数据量下普通的筛素数方法与改进之后的效率对比\n", MAXN);
printf(" by MoreWindows( http://www.2cto.com ) -- --\n\n");
clock_t clockBegin, clockEnd;
clockBegin = clock();
GetPrime_1();
clockEnd = clock();
printf("普通的筛素数方法\t%d毫秒\n", clockEnd - clockBegin);
clockBegin = clock();
GetPrime_2();
clockEnd = clock();
printf("改进的筛素数方法\t%d毫秒\n", clockEnd - clockBegin);
return 0;
}
// 普通的筛素数方法与改进之后的效率对比
// by MoreWindows( http://www.2cto.com )
#include
#include
#include
#include
const int MAXN = 100000000;
bool flag[MAXN];
int primes[MAXN / 3], pi;
// 利用对每个素数的倍数必定不是素数来筛选
void GetPrime_1()
{
int i, j;
pi = 0;
memset(flag, false, sizeof(flag));
for (i = 2; i < MAXN; i++)
if (!flag[i])
{
primes[pi++] = i;
for (j = i; j < MAXN; j += i)
flag[j] = true;
}
}
// 利用了每个合数必有一个最小素因子来筛选
void GetPrime_2()
{
int i, j;
pi = 0;
memset(flag, false, sizeof(flag));
for (i = 2; i < MAXN; i++)
{
if (!flag[i])
primes[pi++] = i;
for (j = 0; (j < pi) && (i * primes[j] < MAXN); j++)
{
flag[i * primes[j]] = true;
if (i % primes[j] == 0)
break;
}
}
}
int main()
{
printf(" 在%d的数据量下普通的筛素数方法与改进之后的效率对比\n", MAXN);
printf(" by MoreWindows( http://www.2cto.com ) -- --\n\n");
clock_t clockBegin, clockEnd;
clockBegin = clock();
GetPrime_1();
clockEnd = clock();
printf("普通的筛素数方法\t%d毫秒\n", clockEnd - clockBegin);
clockBegin = clock();
GetPrime_2();
clockEnd = clock();
printf("改进的筛素数方法\t%d毫秒\n", clockEnd - clockBegin);
return 0;
}
测试结果如图所示：
可以看出，效率有4倍之差。改进还是比较可观。有兴趣的同学可以参考下一篇所讲到的空间压缩技巧来将改进后的筛素数法方进行空间压缩。
文章最后作下小小总结：
1．普通的筛素数的原理是一个素数的倍数必须不是素数。
2．改进的筛素数的原理是每个合数必有一个最小素因子，根据每个最小素因子去访问合数就能防止合数被重复访问。
另外，筛素数法还有很多种改进手段，在数学论坛上可以去研读一下，本文就不再深究了。
摘自 MoreWindows
|