今天我就给大家介绍一下如何高效的求取一个区间的所有素数的方法：
具体参考的是大白书：
如何求取素数呢？其实很简单，思想呢就是找出所有整数P然后，删去2*P，3*P。。。。。就好了？
大该怎么做呢？
我们来真实数据
100以内有25个素数，10^3有168个，10^4有1229个，10^5有9592个，10^6有78498个，10^7有664579个
我们就有实例说明一下：
0~n的所有素数
#include <stdio.h>
#include <time.h>
#include <math.h>
using namespace std;bool a[10000002];int main()
{int i, j;int n = 10000000;for (i = 2;i <= n; i++ ){for ( j = i*2; j <= n; j = j+i ){a[j] = 1;}}int sum = 0;for ( i = 2;i <= n; i++ ){if (a[i] == 0){sum++;}}printf ( "%d\n", sum );printf ( "Time used = %.2lfs\n", (double)clock()/CLOCKS_PER_SEC); //用时
}
以上程序我们会发现，其真实用时会很多有2.51s之多，那么如何改进呢？
这是因为我们有好多重复的步骤在里面。
我下面直接说最快捷的方法了
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <time.h>
#include <math.h>
using namespace std;bool a[10000002];int main()
{int i, j;int n = 10000000;int m = sqrt(n+0.5); //千万要加0.5for (i = 2;i <= m; i++ ){for ( j = i*i; j <= n; j = j+i ) //不要忘了是i*i{if (a[i] == 0) //避免重复a[j] = 1;}}int sum = 0;for ( i = 2;i <= n; i++ ){if (a[i] == 0){sum++;}}printf ( "%d\n", sum );printf ( "Time used = %.2lfs\n", (double)clock()/CLOCKS_PER_SEC);
}
代码菜鸟，如有错误，请多包涵！！！
如果有帮助记得鼓励我一下，谢谢！！！