本文写于2017-10-30，其中的一些思路可能存在问题。本文移至此处时暂未重新学习。

    颓了两天，不过luogu橙名了，虽然并没有A题，luogu的名字颜色评测方案实在是成迷。

    1. //线性筛素数 
    2. #include<iostream>
    3. #define PMAXN 10000000
    5. using namespace std;
    7. bool prime[PMAXN+5];                //prime:0 otherwise:1
    8. int primes[PMAXN+5],prime_num=0;
    10. void make_prime()                    //将合数标记为1，其他没有标记的默认为素数 
    11. {
    12.      prime[0]=prime[1]=1;            //标记0、1为合数 
    13.      for(int i=2;i<=PMAXN;i++)         //从2到PMAXN枚举 
    14.      {
    15.              if(!prime[i])    primes[prime_num++]=i;
    16.                                      //若i至此未被标记，说明i是素数，将其放入素数表 
    17.              for(int j=0;j<prime_num;j++)
    18.                                      //将i与素数表中的所有元素相乘，结果必为合数 
    19.              {
    20.              if(i*primes[j]>PMAXN)    break;
    21.                                      //若当前乘得结果已经超过最大讨论值，直接结束，以防多余运算以及数组越界
    22.                      prime[i*primes[j]]=1;
    23.                      if(i%primes[j]==0)       break;
    24.                                      //若当前i可以被素数表中的当前元素整除，直接枚举下一个i 
    25.              }
    26.      }
    27. }
    29. /*示例:PMAXN=10
    30.   i    prime 0 1 2 3 4 5 6 7 8 9 X        prime_num    primes
    31.   -          1 1                        0            -
    32.   2          1 1 0   1                  1            2
    33.   3          1 1 0 0 1   1     1        2            2 3
    34.   4          1 1 0 0 1   1   1 1        2           2 3
    35.   5          1 1 0 0 1 0 1   1 1 1      3           2 3 5
    36.   ......
    37.   */ 
    39. int main()
    40. {
    41.     make_prime();
    42.     int n,m;
    43.     cin>>n>>m;
    44.     for(int k=1;k<=m;k++)
    45.     {
    46.             int a;
    47.             cin>>a;
    48.             if(prime[a]) cout<<"No"<<endl;
    49.             else         cout<<"Yes"<<endl;
    50.     }
    51.     return 0;
    52. }

    上面的代码对应题目Luogu P3383 【模板】线性筛素数
    ~~
    这里最关键的问题大概就是线性，即保证范围内每一个数（质数和合数）被访问且仅被访问一次。

    所以这里有两项操作值得理解：

    1. prime[i*primes[j]]=1;
    2. if(i%primes[j]==0) break;

    先是第一个，这也是素数筛优化为线性的重要操作之一，也就是筛掉合数时只与当前素数表中的数相乘。如果与一个合数相乘，设这个合数x=pa，其中p是x的质因子，那么ix=ipa必然会在之后i=ia时被筛掉。第二个，如果i%primes[j]==0 则我们可以记i=primes[j]a，如果此时我们继续筛下去，那么下一个筛掉的primes[j]primes[j+1]a会在i=primes[j]*a时被筛掉。

    进一步可以发现，我们可以直接不管全部偶数，当判断到偶数的时候直接判断为合数，在预处理的时候能快一些。也可以在生成素数表的时候传入数据范围，也可以省一些时间。下面就是加一些乱七八糟的优化，比如关闭同步啊（别问我读入优化，我不会写），cout改成puts啊什么的，效果还不错。最后的代码：

    1. //线性筛素数 
    2. #include<iostream>
    3. #include<cstdio>
    5. using namespace std;
    7. bool prime[10000000+5];                    //prime:0 otherwise:1
    8. int primes[10000000+5],prime_num=0;
    10. inline void make_prime(int PMAXN)        //将合数标记为1，其他没有标记的默认为素数 
    11. {
    12.      prime[0]=prime[1]=1;//标记0、1为合数
    13.      prime[2]=0;primes[prime_num++]=2;
    14.      for(register int i=3;i<=PMAXN;i+=2) 
    15.                                          //从3到PMAXN枚举,显然4及以上的偶数都为合数，所以我们直接不考虑它们 
    16.      {
    17.              if(!prime[i])    primes[prime_num++]=i;    
    18.                                          //若i至此未被标记，说明i是素数，将其放入素数表 
    19.              for(register int j=1;j<prime_num;j++)
    20.                                          //将i与素数表中的所有元素（除了2）相乘，结果必为合数 
    21.              {
    22.                      if(i*primes[j]>PMAXN)    break;
    23.                                          //若当前乘得结果已经超过最大讨论值，直接结束，以防多余运算以及数组越界
    24.                      prime[i*primes[j]]=1;
    25.                      if(i%primes[j]==0)       break;
    26.                                          //若当前i可以被素数表中的当前元素整除，直接枚举下一个i 
    27.              }
    28.      }
    29. }
    30. int main()
    31. {
    32.     ios::sync_with_stdio(false);
    33.     int n,m;
    34.     cin>>n>>m;
    35.     make_prime(n+5);
    36.     for(register int k=1;k<=m;k++)
    37.     {
    38.             int a;
    39.             cin>>a;
    40.             if(prime[a]||(a>2&&a%2==0))     puts("No");//如果我们已经标记过a或者a是大于2的偶数，a则为合数。 
    41.             else                  puts("Yes");
    42.     }
    43.     return 0;
    44. }

    还是那道题，10个点，第一个代码1716ms，第二个424ms，感觉自己十分的菜。

    参考了http://blog.csdn.net/nk_test/article/details/46242401，以及luoguP3383的一些题解。