素数筛时间空间优化
时间优化
普通素数筛原理 ：素数的倍数一定不是素数；据此筛选素数。
1void work1()
2{
3 int cnt=0;
4 for(int i=2; i<=n; i++)
5 {
6 if(!flag[i])
7 {
8 prime[cnt++]=i;
9 /**在此处可有个小优化 j=i*i ，但是i*i可能爆int */
10 /**因为>=2 && <i 那部分在 i=2~i-1 中已经标记了 */
11 for(int j=i*2; j<=n; j+=i)
12 flag[j]=1;
13 }
14
15 }
16}
可以发现，在标记某些数字的时候，出现了重复：比如 12，在 i=2 时访问到以后，在 i=3 使也能访问到。
那么就进行改进 ，保证每个数字只被访问一次。
时间优化原理 ：每个合数必有一个最小素因子，根据每个最小素因子去访问合数就能防止重复访问。
1void work2()
2{
3 int cnt=0;
4 memset(flag,0,sizeof(flag));
5 for(int i=2; i<=n; i++)
6 {
7 if(!flag[i])
8 prime[cnt++]=i;
9
10 for(int j=0; (i*prime[j]<=n) && (j<cnt) ; j++)
11 {
12 flag[i*prime[j]]=1;///素数的倍数
13 if(i%prime[j]==0)/**保证每个数只被标记一次*/
14 break;
15 }
16 }
17}
理解 break 语句，当 i = 4 时 ，只标记8，然后跳出；其实可标记的还有：12，20，28……但是，因为 4%2==0 ,所以 i = 6时标记12，i = 10 时标记 20，i = 14 时标记28；
它们均可由 2 * i 得到。
空间优化
空间优化原理：因为 int 型数字有4字节 = 32位，我们可用每一位上的 0 1 来作为标记。
PS：这个方法给我的感觉是操作系统中的分页管理存储方式
1void work3()
2{
3 int cnt=0;
4 for(int i=2;i<=n;i++)
5 {
6 /**相当于分页 ，第 i/32 页第 (i%32) 位*/
7 if(!(f[i/32] &(1<<(i%32))))
8 prime[cnt++]=i;
9
10 for(int j=0;(j<cnt)&&(i*prime[j]<=n);j++ )
11 {
12 int t=i*prime[j];
13 f[t/32] |= (1<<(t%32));
14 if(t==0)
15 break;
16 }
17 }
18}
撸代码：
1#include<stdio.h>
2#include<string.h>
3#define N 10000000
4const int n=1e2;
5bool flag[N];
6int prime[5900000];
7/**
8素数的倍数一定不是素数
9*/
10void work1()
11{
12 int cnt=0;
13 for(int i=2; i<=n; i++)
14 {
15 if(!flag[i])
16 {
17 prime[cnt++]=i;
18 for(int j=i*2; j<=n; j+=i)
19 flag[j]=1;
20 }
21
22 }
23}
24
25/**每个合数必有一个最小素因子，
26根据每个最小素因子去访问合数就能防止重复访问*/
27void work2()
28{
29 int cnt=0;
30 memset(flag,0,sizeof(flag));
31 for(int i=2; i<=n; i++)
32 {
33 //printf("
%d: *********
",i);
34 if(!flag[i])
35 prime[cnt++]=i;
36 for(int j=0; (i*prime[j]<=n) && (j<cnt) ; j++)
37 {
38 flag[i*prime[j]]=1;///素数相乘的倍数
39 // printf("%d ",i*prime[j]);
40 if(i%prime[j]==0)/**保证每个数只被标记一次*/
41 break;
42 }
43 }
44}
45/**空间优化*/
46/***/
47int f[N/32];
48void work3()
49{
50 int cnt=0;
51 for(int i=2;i<=n;i++)
52 {
53 /**相当于分页 ，第 i/32 页第 (i%32) 位*/
54 if(!(f[i/32] &(1<<(i%32))))
55 prime[cnt++]=i;
56
57 for(int j=0;(j<cnt)&&(i*prime[j]<=n);j++ )
58 {
59 int t=i*prime[j];
60 f[t/32] |= (1<<(t%32));
61 if(t==0)
62 break;
63 }
64 }
65}
66int main()
67{
68 work3();
69 for(int i=0; i<100; i++)
70 printf("%d ",prime[i]);
71 return 0;
72}