根据题目描述，需要从 1 到 n 中选取尽可能多的整数，使得任意两个不同的整数互质，并输出最大数量。

解题思路：

1. 互质的条件是两个数的最大公因数为 1。为了最大化选取数量，应尽可能选择质数，因为质数之间一定互质，且 1 与所有数互质。
2. 每个大于 1 的整数至少有一个质因数，如果选取的整数中包含相同的质因数，则它们不互质。因此，所有选取的大于 1 的整数必须拥有互不相同的质因数。
3. 不超过 n 的质数个数记为 π(n)，则最大数量为 1（包含 1）加上 π(n)，即 1 + π(n)。
4. 可以通过埃拉托斯特尼筛法计算不超过 n 的质数个数。

代码实现（C++）：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    vector<bool> is_prime(n + 1, true);
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            cnt++;
            for (int j = i + i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    cout << cnt + 1 << endl;
    return 0;
}

示例说明：

• 输入 6，不超过 6 的质数有 2、3、5，共 3 个，加上 1 得 4，输出 4。
• 输入 9，不超过 9 的质数有 2、3、5、7，共 4 个，加上 1 得 5，输出 5。

该算法时间复杂度为 O(n log log n)，在 n ≤ 10⁵ 时高效可行。