数据结构与算法-线性筛素数

• 任何一个大于1的整数都可以唯一分解成有限个质数的乘积(数学归纳法可证)。
  那么这个数可以被唯一分解成最小质因子和最大剩余因子的乘积(就是除开最小质因子剩余的数)。
  欧氏筛的原理就是这样，它保证了筛法的唯一性。
  其中Prime[j]是最小质因子，i是最大剩余因子。

• 如果i%Prime[j]==0，即i=t*Prime[j]。

  当标记 i*Prime[j+1] 时，
  i*Prime[j+1]这个数并不是最小质因子与最大剩余因子的乘积的形式，
  因为i可以被拆成t*Prime[j]，说明Prime[j+1]不是这个数的最小质因子(Prime是升序数组)，
  i*Prime[j+1]这个数应该被拆成 (t*Prime[j+1])*Prime[j]，
  这样才是最小质因子与最大剩余因子的乘积的形式，
  其中最小质因子为Prime[j]，最大剩余因子为t*Prime[j+1]，
  也就是说 i*Prime[j+1] 这个数将在循环遍历到 i=t*Prime[j+1] 时被标记。

  同理，当标记 i*Prime[j+k]时，
  i*Prime[j+k]这个数并不是最小质因子与最大剩余因子的乘积的形式，
  因为i可以被拆成t*Prime[j]，说明Prime[j+k]不是这个数的最小质因子(Prime是升序数组)，
  i*Prime[j+k]这个数应该被拆成 (t*Prime[j+k])*Prime[j]，
  …
  也就是说 i*Prime[j+k] 这个数将在循环遍历到 i=t*Prime[j+k] 时被标记。

  所以一旦i%Prime[j]==0，i就可以被拆成t*Prime[j]，
  不再满足数拆分成最小质因子与最大剩余因子的乘积的形式，
  就break退出该层循环。

  也就是说，如果一个数被标记，那肯定是由它的最小质因子与最大剩余因子的乘积标记的,这是标记的唯一性。
  又因为任何一个大于1的整数都可以唯一分解成有限个质数的乘积，而Prime保存了当前发现的所有质数，
  当计算进行下去，所有范围的数都可以被分解成***形式，这是标记的无遗漏性。
  真是合情合理。

#include 
#include 
#include 
using namespace std;
#define reject  std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define pause   cout<<"n";system("pause")

template 
void PrintArray(T* Array) {
    for (int i = 0; Array[i]; ++i) {
        cout << Array[i] << " ";
    }
    cout << "n";
}

const int Max = static_cast(1e8);
int N,Q,K;
int Prime[Max];
int Index=-1;
bool IsNotPrime[Max];
//埃氏筛
void DoPrimeAi() {
    IsNotPrime[2]=false;
    for (int i=2;i<=N;++i) {
        if (IsNotPrime[i]==false) {
            Prime[++Index]=i;
            //质数的倍数都是合数
            for (int j=i+i;j<=N;j+=i) {
                IsNotPrime[j]=true;
            }
        }
    }
}
//欧氏筛
void DoPrimeOu() {
    IsNotPrime[2]=false;
    for (int i=2;i<=N;++i) {
        if (IsNotPrime[i]==false) {  
            Prime[++Index]=i;
        }
        for (int j=0;j<=Index&&(i*Prime[j]<=N);++j) {

            //任何一个大于1的整数都可以唯一分解成有限个质数的乘积。
            //那么这个数可以被唯一分解成最小质因子和最大剩余因子的乘积。
            //欧氏筛的原理就是这样，它保证了筛法的唯一性。
            //其中Prime[j]是最小质因子，i是最大剩余因子。
            IsNotPrime[(i*Prime[j])]=true;

            //如果i%Prime[j]==0，即i=t*Prime[j]。
            
            //当标记 i*Prime[j+1] 时，
            // i*Prime[j+1]这个数并不是最小质因子与最大剩余因子的乘积的形式，
            // 因为i可以被拆成t*Prime[j]，说明Prime[j+1]不是这个数的最小质因子(Prime是升序数组)，
            // i*Prime[j+1]这个数应该被拆成 (t*Prime[j+1])*Prime[j]，
            //这样才是最小质因子与最大剩余因子的乘积的形式，
            //其中最小质因子为Prime[j]，最大剩余因子为t*Prime[j+1]，
            //也就是说 i*Prime[j+1] 这个数将在循环遍历到 i=t*Prime[j+1] 时被标记。
            
            //同理，当标记 i*Prime[j+k]时，
            // i*Prime[j+k]这个数并不是最小质因子与最大剩余因子的乘积的形式，
            // 因为i可以被拆成t*Prime[j]，说明Prime[j+k]不是这个数的最小质因子(Prime是升序数组)，
            // i*Prime[j+k]这个数应该被拆成 (t*Prime[j+k])*Prime[j]，
            // ...
            // 也就是说 i*Prime[j+k] 这个数将在循环遍历到 i=t*Prime[j+k] 时被标记。
            
            // 所以一旦i%Prime[j]==0，i就可以被拆成t*Prime[j]，
            // 不再满足数拆分成最小质因子与最大剩余因子的乘积的形式，
            // 就break退出该层循环。
             
            // 也就是说，如果一个数被标记，那肯定是由它的最小质因子与最大剩余因子的乘积标记的,这是标记的唯一性。
            // 又因为任何一个大于1的整数都可以唯一分解成有限个质数的乘积，而Prime保存了当前发现的所有质数，
            // 当计算进行下去，所有范围的数都可以被分解成***形式，这是标记的无遗漏性。
            // 真是合情合理。
            if (i%Prime[j]==0) {
                break;
            }
        }
    }
}
int main() {
    reject;
    cin>>N>>Q;
    DoPrimeOu();
    //PrintArray(Prime);
    for (int i=1;i<=Q;++i) {
        cin>> K;
        cout<