3
2 4 6
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

4
2 3 4 9
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

# 读取输入
n = int(input())  # 读取数组大小
arr = list(map(int, input().split()))  # 读取数组元素

# 计算最少颜色组数的函数
def find_colors(nums):
    if not nums:  # 递归终止条件：如果数组为空，返回0
        return 0

    nums.sort()  # 排序数组，确保最小的数优先处理
    base = nums[0]  # 选取最小的数作为当前颜色组的基准

    # 过滤掉所有是 base 倍数的数，剩余的数进入下一个递归
    filtered = [num for num in nums if num % base != 0]

    # 1 (当前组) + 递归计算剩余数的颜色组数
    return 1 + find_colors(filtered)

# 输出最少颜色组数
print(find_colors(arr))

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21

java解法

• 解题思路
• 本程序的目标是计算数组可以被分成的最少颜色组数，其中：

任何一个颜色组中的所有数字，都不能是另一个数字的倍数。
需要最少的颜色数，即尽可能少的组数。
解题步骤
读取输入

读取整数 n，表示数组的元素个数。
读取 n 个整数，并存入 numbers 数组。
计算最少颜色组数 calculateMinColors(n, numbers)

排序 numbers：先对数组进行升序排序，确保较小的数先被考虑。
创建布尔数组 used[]：
used[i] == true 表示 numbers[i] 已经被归类到某个颜色组，不需要再考虑。
遍历 numbers 并标记倍数：
如果 numbers[i] 没有被使用，增加颜色组 colorCount。
遍历 numbers[j]（j > i），如果 numbers[j] 是 numbers[i] 的倍数，则将其标记为已使用 used[j] = true。
返回 colorCount 作为最少颜色组数

统计出最小的颜色组数，并返回

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组大小
        int n = Integer.parseInt(scanner.nextLine());

        // 读取数组元素并转换为整数数组
        int[] numbers = Arrays.stream(scanner.nextLine().split(" "))
                              .mapToInt(Integer::parseInt)
                              .toArray();

        // 计算最少颜色组数并输出
        System.out.println(calculateMinColors(n, numbers));
    }

    public static int calculateMinColors(int n, int[] numbers) {
        Arrays.sort(numbers); // 对数组进行排序，确保较小的数先处理
        int colorCount = 0; // 记录最少颜色组数
        boolean[] used = new boolean[n]; // 标记数组，记录哪些数字已归类

        // 遍历所有数字，确定颜色组
        for (int i = 0; i < n; i++) {
            if (used[i]) continue; // 如果当前数字已归类，则跳过

            colorCount++; // 发现一个新的颜色组

            // 遍历剩余的数字，标记所有当前数字的倍数
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && numbers[j] % numbers[i] == 0) {
                    used[j] = true; // 标记该数字已归类
                }
            }
        }

        return colorCount; // 返回最少颜色组数
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">