质数：试除 → 埃氏筛 → 线性筛

// 标准答案 —— 试除法：一个数一个数地问「它是质数吗」
//
// 为什么它存在：
//   ① 它是对拍里的标准答案，思路和「筛」**完全不同** ——
//      筛法是**从质数出发去划掉合数**，试除法是**对每个数单独审问一遍**
//      （第 9、15 章那条规矩：标准答案最好换个想法写）。
//   ② ★ 它同时是这一章的反面教材：判断一个数要试到 √x，
//      把 1..n 全问一遍就是 **O(n√n)** —— n = 10⁶ 时已经要按秒算了。
//
// ⚠ 两个边界，题面里都写死了，这里也要写死：
//   · **1 不是质数**（它只有一个约数）；
//   · 最小质因子：x = 1 时题面规定输出 0，x 是质数时它自己就是最小质因子。
//
// 复杂度 O(n√n + m√n)。

#include <bits/stdc++.h>
using namespace std;

/** x 的最小质因子；x = 1 时返回 0 */
int minPrimeFactor(int x) {
    if (x == 1) return 0;
    for (int i = 2; (long long)i * i <= x; i++)      // ⚠ i*i 要用 long long 兜住
        if (x % i == 0) return i;
    return x;                                        // 没被整除过 ⇒ 它自己是质数
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    int cnt = 0, mx = 0;
    for (int x = 2; x <= n; x++)
        if (minPrimeFactor(x) == x) { cnt++; mx = x; }

    string out = to_string(cnt);
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        out += to_string(minPrimeFactor(x));
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(mx);
    out += '\n';

    cout << out;
    return 0;
}

// ⚠ 这不是错误版本 —— 埃拉托色尼筛（埃氏筛）。答案和正解**逐字节相同**，只是划的次数多。
//
// 想法比线性筛还要老实：**从 2 开始，每碰到一个没被划掉的数，就把它的倍数全划掉。**
//
//   ```cpp
//   for (int i = 2; i <= n; i++)
//       if (!comp[i])                                  // i 是质数
//           for (long long j = (long long)i * i; j <= n; j += i)   // ★ 从 i² 开始就够了
//               comp[j] = true;
//   ```
//
// ★ **为什么内层能从 i² 开始，而不是 2i？**
//   比 i² 小的 i 的倍数是 k·i（k < i），它一定有一个比 i 小的质因子 ——
//   那个质因子在更早的一轮就已经把它划掉了。**所以 2i … (i−1)i 全是白划。**
//   ⚠ 但这只是个常数级的省事，**它改变不了复杂度**（slowErat.cpp 把两者并排量了出来）。
//
// ⚠ 而它和线性筛的真正差别在这儿：
//   **一个合数有几个不同的质因子，就会被划几次**（12 = 2²·3 会被 2 和 3 各划一次）。
//   总次数是 **Σ n/p ≈ n·ln ln n**，也就是 O(n log log n) —— 比线性多一个几乎不涨的因子。
//
// ⚠⚠ **可它求不出最小质因子**（题面第二问要的那个）：
//   `comp[j] = true` 只记了「j 是合数」，没记「是谁划的」；
//   而且 j 会被好几个质数反复划，**最后一次划它的那个并不是最小的**。
//   所以这一份得再花一次力气：拿筛出来的质数表去试除。
//   ★ 这正是线性筛白送的东西 —— 第 7 步会把这件事说清楚。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000005;
bool comp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 2; i <= n; i++)
        if (!comp[i])
            for (long long j = (long long)i * i; j <= n; j += i)   // ★ 从 i² 开始
                comp[j] = true;

    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (!comp[i]) primes.push_back(i);

    string out = to_string((int)primes.size());
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        int mp = 0;
        if (x > 1) {
            mp = x;                                // ⚠ 求最小质因子只能再试除一遍
            for (int p : primes) {
                if ((long long)p * p > x) break;
                if (x % p == 0) { mp = p; break; }
            }
        }
        out += to_string(mp);
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(primes.empty() ? 0 : primes.back());
    out += '\n';

    cout << out;
    return 0;
}

// 正解 —— 线性筛（欧拉筛）：**每个合数只被它的最小质因子筛掉一次**
//
// ============ ★ 关键一步：那句 break 站在哪儿 ============
//
//   ```cpp
//   for (int i = 2; i <= n; i++) {
//       if (!minp[i]) { minp[i] = i; primes.push_back(i); }     // i 没被划掉 ⇒ 它是质数
//       for (int p : primes) {
//           if ((long long)i * p > n) break;
//           minp[i * p] = p;                    // ★ 用 p 去划掉 i*p，而 p 就是 i*p 的最小质因子
//           if (i % p == 0) break;              // ★★ 全章的灵魂，就是这一句
//       }
//   }
//   ```
//
//   ★ **为什么那句 `if (i % p == 0) break;` 保证了「每个合数只被划一次」？**
//
//   两句话：
//     ① **每个合数都被划到了**：设合数 c 的最小质因子是 p，写 c = i·p（i = c/p）。
//        因为 p 是 c 的最小质因子，所以 i 的每个质因子都 ≥ p ——
//        于是内层循环走到 p 的时候还没 break（前面那些质数都比 p 小、都不整除 i），
//        c 就在这一步被划掉了。
//     ② **每个合数只被划一次**：内层用 p 划 i·p 时，p ≤ i 的最小质因子，
//        所以 **p 一定是 i·p 的最小质因子**。而一个合数的最小质因子只有一个、
//        对应的 i = c/p 也只有一个 ⇒ **(i, p) 这一对是唯一的**，所以只会被划一次。
//        而那句 break 干的正是「一旦 p 整除 i，就不许再往大的质数走」——
//        再走下去，划的那个 i·p' 的最小质因子就不是 p' 了（是 p），就重复了。
//
//   ⇒ **总的划掉次数 = 合数个数 = O(n)。这就是「线性」两个字的全部含义。**
//
//   ⚠ 对比埃氏筛：它对每个质数 p 把 p²、p²+p、… 全划一遍，
//     一个合数有几个不同的质因子就被划几次 ⇒ **O(n log log n)**。
//     两者答案完全一样，差的只是次数 —— 这一章又是一个「对拍看不见慢」的现场。
//
// ============ ★ 顺手白送的东西：最小质因子 ============
//
//   `minp[x]` 在筛的过程中天然就填好了，一分钱不用多花。
//   有了它，**分解质因数就从 O(√x) 掉到 O(log x)**（一路除最小质因子）——
//   题面第二问要的正是它。
//
// 复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000005;
int minp[MAXN];                                    // minp[x]：x 的最小质因子（0 = 还没被划到）
vector<int> primes;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 2; i <= n; i++) {
        if (!minp[i]) { minp[i] = i; primes.push_back(i); }   // 没被划掉 ⇒ 质数
        for (int p : primes) {
            if ((long long)i * p > n) break;       // ⚠ i*p 会超 int，要用 long long 判
            minp[i * p] = p;                       // ★ p 就是 i*p 的最小质因子
            if (i % p == 0) break;                 // ★★ 全章的灵魂
        }
    }

    string out = to_string((int)primes.size());
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        out += to_string(x == 1 ? 0 : minp[x]);    // ⚠ 题面规定 x = 1 输出 0
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(primes.empty() ? 0 : primes.back());
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：那句 break **站在标记之前**
//
//   ```
//   if (i % p == 0) break;      ← ✗ 先 break
//   minp[i * p] = p;            ← 于是这一次该划的没划
//   ```
//
// 靠什么现形：i 的最小质因子 p 那一次被跳过了 ——
//   而 `i·p`（p = minp[i]）**只有这一次机会被划到**（那是它唯一的 (i,p) 分解）。
//   ⇒ 4、8、9、12、16… 这些「最小质因子的平方能整除它」的数会漏网。
// ★ 和 wrongNoBreak 正好是一对：**一句话，站前面站后面，错的方向正相反。**
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000005;
int minp[MAXN];                                    // minp[x]：x 的最小质因子（0 = 还没被划到）
vector<int> primes;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 2; i <= n; i++) {
        if (!minp[i]) { minp[i] = i; primes.push_back(i); }   // 没被划掉 ⇒ 质数
        for (int p : primes) {
            if ((long long)i * p > n) break;       // ⚠ i*p 会超 int，要用 long long 判
            if (i % p == 0) break;                 // ✗ 先 break 了
            minp[i * p] = p;                       // ✗ 于是这一次该划的没划
        }
    }

    string out = to_string((int)primes.size());
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        out += to_string(x == 1 ? 0 : minp[x]);    // ⚠ 题面规定 x = 1 输出 0
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(primes.empty() ? 0 : primes.back());
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：`minp[i * p] = p` 写成了 `minp[i * p] = minp[i]`（想当然）
//
//   「i·p 的最小质因子，不就是 i 的最小质因子吗？」—— **不是。**
//   内层循环里 p 是从小到大取的，而 break 保证了 **p ≤ minp[i]**，
//   所以 i·p 的最小质因子是 **p**，不是 minp[i]。
//
// 靠什么现形：只要有一次 **p < minp[i]** 就错（比如 i = 9、p = 2 时 i·p = 18，
//   最小质因子是 2 而不是 3）。⇒ 要询问**含小质因子的合数**。
// ⚠ 而第一行「质数个数」和第三行「最大质数」它都是对的 —— **只有第二行错**。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000005;
int minp[MAXN];                                    // minp[x]：x 的最小质因子（0 = 还没被划到）
vector<int> primes;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 2; i <= n; i++) {
        if (!minp[i]) { minp[i] = i; primes.push_back(i); }   // 没被划掉 ⇒ 质数
        for (int p : primes) {
            if ((long long)i * p > n) break;       // ⚠ i*p 会超 int，要用 long long 判
            minp[i * p] = minp[i];                 // ✗ 想当然：i·p 的最小质因子是 p，不是 minp[i]
            if (i % p == 0) break;                 // ★★ 全章的灵魂
        }
    }

    string out = to_string((int)primes.size());
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        out += to_string(x == 1 ? 0 : minp[x]);    // ⚠ 题面规定 x = 1 输出 0
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(primes.empty() ? 0 : primes.back());
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：埃氏筛内层写成 `j < n`（少划了 n 本身）
//
// 靠什么现形：★ **n 本身是合数，而且它的最小质因子的平方 ≤ n** —— 那时候 n 没被划掉，
//   于是它被当成质数，第一行的计数多 1、第三行的「最大质数」直接错成 n。
//   ⚠ n 是奇数还是偶数、是质数还是合数，**随机取一个 n 就有一半机会碰上** ——
//   可如果生成器顺手只取偶数 n，或者只取一两个固定的 n，这个 bug 就永远见不到。
// ★ 「区间的右端点少一格」是这本书里出现次数最多的一类 bug（第 6、23、38 章都有）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000005;
bool comp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 2; i <= n; i++)
        if (!comp[i])
            for (long long j = (long long)i * i; j < n; j += i)    // ✗ 少了一个等号，n 自己没划到
                comp[j] = true;

    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (!comp[i]) primes.push_back(i);

    string out = to_string((int)primes.size());
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        int mp = 0;
        if (x > 1) {
            mp = x;                                // ⚠ 求最小质因子只能再试除一遍
            for (int p : primes) {
                if ((long long)p * p > x) break;
                if (x % p == 0) { mp = p; break; }
            }
        }
        out += to_string(mp);
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(primes.empty() ? 0 : primes.back());
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：试除写成 `i * i < x`（漏掉了完全平方数）
//
//   本来该是 `i * i <= x`。少一个等号，**x 正好是某个质数的平方时就判错了**：
//   4、9、25、49、121… 会被当成质数。
//
// 靠什么现形：★ 询问里要出现 **质数的平方**（或者 n 足够大时第一行的计数会多出来一截）。
//   ⚠ 随机询问撞到 4/9/25 的概率同样极低 ⇒ 生成器要**专门塞小数和平方数**。
#include <bits/stdc++.h>
using namespace std;

/** x 的最小质因子；x = 1 时返回 0 */
int minPrimeFactor(int x) {
    if (x == 1) return 0;
    for (int i = 2; (long long)i * i < x; i++)       // ✗ 少了一个等号
        if (x % i == 0) return i;
    return x;                                        // 没被整除过 ⇒ 它自己是质数
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    int cnt = 0, mx = 0;
    for (int x = 2; x <= n; x++)
        if (minPrimeFactor(x) == x) { cnt++; mx = x; }

    string out = to_string(cnt);
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        out += to_string(minPrimeFactor(x));
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(mx);
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：**x = 1 时输出 1**（把 1 当成了「自己的最小质因子」）
//
//   题面写死了「x = 1 时输出 0」，因为 **1 没有质因子**（它也不是质数）。
//   把 `minp[1]` 填成 1 是最自然不过的手滑 —— 而且它**只影响这一种询问**：
//   第一行的质数个数、第三行的最大质数，它一个字都不错。
//
// 靠什么现形：★ 询问里必须出现 **x = 1**。
//   ⚠ 而 1 ≤ x ≤ n、n 到 10⁷ 时，随机询问撞到 1 的概率是**一千万分之一** ——
//   ⇒ 生成器必须**专门往询问里塞 1**。这是这一章「顺手写法」的现场。
// ★ 0 和 1 是数学题里永远要单独想一遍的两个数（第 40 章立的那条：算法越短，
//   风险越往「取模、溢出、负数、0 和 1」上转移）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000005;
int minp[MAXN];                                    // minp[x]：x 的最小质因子（0 = 还没被划到）
vector<int> primes;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    minp[1] = 1;                                   // ✗ 题面规定 x = 1 要输出 0
    for (int i = 2; i <= n; i++) {
        if (!minp[i]) { minp[i] = i; primes.push_back(i); }   // 没被划掉 ⇒ 质数
        for (int p : primes) {
            if ((long long)i * p > n) break;       // ⚠ i*p 会超 int，要用 long long 判
            minp[i * p] = p;                       // ★ p 就是 i*p 的最小质因子
            if (i % p == 0) break;                 // ★★ 全章的灵魂
        }
    }

    string out = to_string((int)primes.size());
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        out += to_string(minp[x]);                 // ✗ 忘了 x = 1 那条特例
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(primes.empty() ? 0 : primes.back());
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：**第三行没判「一个质数都没有」的情况**
//
//   题面允许 `n = 1` —— 这时候 1..n 里一个质数都没有，第三行该输出 0。
//   `primes.back()` 在空表上是**未定义行为**：跑出来的那个数是内存里的垃圾。
//
// 靠什么现形：★ 生成器必须造出 **n = 1**。
//   ⚠ 而「顺手」写的生成器多半是 `n = rnd(2, 50)` —— 因为「n ≥ 2 才有质数嘛」。
//   ★ 那正是第 27~40 章那条「顺手写法会悄悄给数据加一条题目里没有的性质」的第十三次：
//     这次加的性质是「**n 至少是 2**」。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000005;
int minp[MAXN];                                    // minp[x]：x 的最小质因子（0 = 还没被划到）
vector<int> primes;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 2; i <= n; i++) {
        if (!minp[i]) { minp[i] = i; primes.push_back(i); }   // 没被划掉 ⇒ 质数
        for (int p : primes) {
            if ((long long)i * p > n) break;       // ⚠ i*p 会超 int，要用 long long 判
            minp[i * p] = p;                       // ★ p 就是 i*p 的最小质因子
            if (i % p == 0) break;                 // ★★ 全章的灵魂
        }
    }

    string out = to_string((int)primes.size());
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        out += to_string(x == 1 ? 0 : minp[x]);    // ⚠ 题面规定 x = 1 输出 0
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(primes.back());               // ✗ 没判空：n = 1 时这里是未定义行为
    out += '\n';

    cout << out;
    return 0;
}

// 正解 —— 线性筛（欧拉筛）：**每个合数只被它的最小质因子筛掉一次**
//
// ============ ★ 关键一步：那句 break 站在哪儿 ============
//
//   ```cpp
//   for (int i = 2; i <= n; i++) {
//       if (!minp[i]) { minp[i] = i; primes.push_back(i); }     // i 没被划掉 ⇒ 它是质数
//       for (int p : primes) {
//           if ((long long)i * p > n) break;
//           minp[i * p] = p;                    // ★ 用 p 去划掉 i*p，而 p 就是 i*p 的最小质因子
//           if (i % p == 0) break;              // ★★ 全章的灵魂，就是这一句
//       }
//   }
//   ```
//
//   ★ **为什么那句 `if (i % p == 0) break;` 保证了「每个合数只被划一次」？**
//
//   两句话：
//     ① **每个合数都被划到了**：设合数 c 的最小质因子是 p，写 c = i·p（i = c/p）。
//        因为 p 是 c 的最小质因子，所以 i 的每个质因子都 ≥ p ——
//        于是内层循环走到 p 的时候还没 break（前面那些质数都比 p 小、都不整除 i），
//        c 就在这一步被划掉了。
//     ② **每个合数只被划一次**：内层用 p 划 i·p 时，p ≤ i 的最小质因子，
//        所以 **p 一定是 i·p 的最小质因子**。而一个合数的最小质因子只有一个、
//        对应的 i = c/p 也只有一个 ⇒ **(i, p) 这一对是唯一的**，所以只会被划一次。
//        而那句 break 干的正是「一旦 p 整除 i，就不许再往大的质数走」——
//        再走下去，划的那个 i·p' 的最小质因子就不是 p' 了（是 p），就重复了。
//
//   ⇒ **总的划掉次数 = 合数个数 = O(n)。这就是「线性」两个字的全部含义。**
//
//   ⚠ 对比埃氏筛：它对每个质数 p 把 p²、p²+p、… 全划一遍，
//     一个合数有几个不同的质因子就被划几次 ⇒ **O(n log log n)**。
//     两者答案完全一样，差的只是次数 —— 这一章又是一个「对拍看不见慢」的现场。
//
// ============ ★ 顺手白送的东西：最小质因子 ============
//
//   `minp[x]` 在筛的过程中天然就填好了，一分钱不用多花。
//   有了它，**分解质因数就从 O(√x) 掉到 O(log x)**（一路除最小质因子）——
//   题面第二问要的正是它。
//
// 复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000005;
int minp[MAXN];                                    // minp[x]：x 的最小质因子（0 = 还没被划到）
vector<int> primes;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 2; i <= n; i++) {
        if (!minp[i]) { minp[i] = i; primes.push_back(i); }   // 没被划掉 ⇒ 质数
        for (int p : primes) {
            if ((long long)i * p > n) break;       // ⚠ i*p 会超 int，要用 long long 判
            minp[i * p] = p;                       // ★ p 就是 i*p 的最小质因子
            if (i % p == 0) break;                 // ★★ 全章的灵魂
        }
    }

    string out = to_string((int)primes.size());
    out += '\n';
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        out += to_string(x == 1 ? 0 : minp[x]);    // ⚠ 题面规定 x = 1 输出 0
        out += (i == m - 1 ? '\n' : ' ');
    }
    if (m == 0) out += '\n';
    out += to_string(primes.empty() ? 0 : primes.back());
    out += '\n';

    cout << out;
    return 0;
}