一. 理解
-
任何一个大于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 <iomanip>
#include <iostream>
#include <cmath>
using namespace std;
#define reject std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define pause cout<<"\n";system("pause")
template <typename T>
void PrintArray(T* Array) {
for (int i = 0; Array[i]; ++i) {
cout << Array[i] << " ";
}
cout << "\n";
}
const int Max = static_cast<int>(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<<Prime[K-1]<<"\n";
}
pause;
return 0;
}
