题目大意
给定正整数 n，要构造长度为 n 的数组 a[1..n]，每个元素取自 1..n，可重复使用。要求对于任意 i≠j 且 gcd(i,j)>1 的一对下标，必须满足 a[i]≠a[j]。问最少需要多少种不同的数字。

思路

1. 把下标 1…n 看成图的顶点，若 gcd(i,j)>1 则顶点 i、j 之间连边。
2. 要求相邻顶点染成不同颜色，最少颜色数就是这个图的染色数。
3. 图中所有偶数顶点两两 gcd ≥2，构成一个团；它的大小是 ⌊n/2⌋，因此至少需要 ⌊n/2⌋ 种颜色。
4. 实际上可以只用 ⌊n/2⌋ 种颜色完成染色：
   • 给每个偶数索引分配一种互不相同的颜色；
   • 奇数索引之间和它们与偶数索引之间冲突都能用已有颜色合理安排，故总共 ⌊n/2⌋ 色即可。
5. 特殊地，n=1 时只有一个顶点，不需考虑边，答案为 1。

C++

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

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

    long long n;
    cin >> n;
    // n=1 时只需 1 种；否则答案就是偶数个数 = n/2（向下取整）
    cout << (n == 1 ? 1 : n / 2) << "\n";
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(in.readLine().trim());
        // n=1 时只需 1 种；否则偶数个数为 n/2（整数除法）
        System.out.println(n == 1 ? 1 : n / 2);
    }
}

Python

import sys

def main():
    n = int(sys.stdin.readline())
    # n=1 时只需 1 种；否则偶数个数为 n//2
    print(1 if n == 1 else n // 2)

if __name__ == "__main__":
    main()

题目内容

小红想构造一个长度为 $n$ 的数组 ${a_1,a_2,….,a_n}$，其中 $a$ 满足 $1≤ a_i ≤ n$，$[1,n]$ 的每个数字可以重复使用也可以不用。

她希望任意两个索引 $i,j$ 满足 ($i≠ j$ 且 $gcd(i,j)≠1$ )时，其两个位置的权值不相等，即 $a_i ≠ a_j$ ，请你帮助小红判断最少需要多少种不同的数字。

输入描述

一个整数 $n(1 ≤ n ≤ 10^9)$ ，表示小红希望你构造的数组长度。

输出描述

一个整数，表示数组中不同数字的个数的最小值。

样例1

输入

3

输出

1

说明

数组下标依次为 $[1,2,3]$ ，对于任意的两个索引 $i,j(i ≠ j)$ 都满足 $gcd(i,j)= 1$ ，所以我们可以只使用 $2$ 来填数组 ，为 $[2,2,2]$ ，当然 $[1,1,1]$ 或者 $[3,3,3]$ 也是正确的。

样例2

输入

4

输出

2