2026 华为OD机试真题9月16日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

已知所有大于 1 的整数都可以被唯一分解成质数的乘积，我们把这组质数称为该整数的质因子；如：12=2×2×3，12 的质因子为 [2,3]，7=1×7，7 的质因子为 [7]。

现给定一个正整数 n 和一个质数列表 nums（数字严格递增），请统计数字 1∼n 之中，有哪些数字的质因子仅出现在列表 nums 内，返回符合条件的数字数量。

注意：数字 1 无质因子，作为符合条件的数字纳入统计。

质数定义：大于 1 的自然数，除了 1 和它自身外不能被其他自然数整除的数。

数据范围：整数 n 范围：1≤n≤10^12；列表 nums 长度 m 范围：1≤m≤5。

2026 华为OD机试真题9月16日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

输入分为三行：第一行是正整数 n，第二行是质数列表长度 m，第三行是以英文逗号分隔的质数列表 nums。

输出描述

输出一个整数，表示 1∼n 中质因子仅出现在列表 nums 内的正整数数量。

示例1

输入

10
2
2,3

输出

7

说明

输入参数：上限 n=10，质数个数 m=2，允许质因子列表 [2,3]

统计所有 ≤10 且质因子仅为 2、3 的正整数：

1（无质因子）、2、3、4、6、8、9，共 7 个。

示例2

输入

15
3
2,3,5

输出

11

说明

输入参数：上限 n=15，质数个数 m=3，允许质因子列表 [2,3,5]

统计结果包含 1、2、3、4、5、6、8、9、10、12、15，共 11 个。

解题思路

核心思想

如果一个数字的质因子只能来自 nums，那么它一定可以表示成：

p1^e1 × p2^e2 × ... × pm^em

其中每个指数 ei 都是非负整数。数字 1 对应所有指数都为 0，因此自然会被枚举一次。

从左到右处理质数列表。固定前面质数形成的乘积后，让当前质数的指数从 0 开始逐步增加，只要乘积不超过 n，就递归处理下一个质数。到达所有质数后，说明得到了一组合法指数，答案加 1。

这种方式直接统计指数组合数量，不需要像参考实现一样保存每一轮所有中间数字，额外空间只与质数个数有关。

算法步骤

1. 令当前乘积为 1，从第一个允许质数开始递归。
2. 在递归层 index 中，依次尝试当前质数的 0 次、1 次、2 次幂……。
3. 如果当前乘积不超过 n，则继续递归处理下一个质数。
4. 如果乘上下一次当前质数会超过 n，停止当前层循环，避免溢出和无效计算。
5. 当所有质数都处理完时，找到一个合法数字，返回 1。
6. 汇总所有分支的计数，得到最终结果。

复杂度分析

设最终符合条件的数字数量为 K，允许质数数量为 m。每个合法数字对应一条递归路径，时间复杂度为 O(Km)，额外空间复杂度为 O(m)。由于 m≤5，递归深