1. 题目解析与核心思路这道题目来自蚂蚁集团2026年暑期实习开发岗的笔试环节考察的是基础的数论知识和编程实现能力。题目要求我们处理质数与合数的相关问题这在算法面试中属于中等偏下难度的题目但非常能考察候选人的基础编码能力和数学思维。1.1 题目要求理解题目通常会给出一个具体的数值范围或条件要求我们判断某个数是否为质数生成某个范围内的所有质数计算质数或合数的某种统计特征对质数和合数进行某种组合操作这类问题的核心在于高效实现质数判断和生成算法同时处理好边界条件和特殊情况。1.2 质数判断的优化思路最基础的质数判断方法是试除法即检查该数是否能被2到√n之间的整数整除。但这种方法的复杂度是O(√n)当需要处理大量数字时会非常低效。我们可以采用以下优化策略预处理法使用埃拉托斯特尼筛法埃氏筛预先计算出范围内的所有质数6n±1法则除了2和3所有质数都可以表示为6n±1的形式米勒-拉宾素性测试对于极大数的概率性判断方法提示在笔试环境下通常使用埃氏筛就能满足性能要求且实现简单不易出错2. Java实现方案2.1 基础质数判断public static boolean isPrime(int n) { if (n 1) return false; if (n 2) return true; if (n % 2 0) return false; for (int i 3; i * i n; i 2) { if (n % i 0) { return false; } } return true; }2.2 埃拉托斯特尼筛法实现public static ListInteger sieveOfEratosthenes(int limit) { boolean[] isPrime new boolean[limit 1]; Arrays.fill(isPrime, true); isPrime[0] isPrime[1] false; for (int i 2; i * i limit; i) { if (isPrime[i]) { for (int j i * i; j limit; j i) { isPrime[j] false; } } } ListInteger primes new ArrayList(); for (int i 2; i limit; i) { if (isPrime[i]) { primes.add(i); } } return primes; }2.3 性能优化技巧位图优化使用BitSet代替boolean数组可以减少内存使用分段筛法处理极大范围时可以分段进行筛法处理并行计算对于多核环境可以将筛法过程并行化3. C实现方案3.1 基础质数判断bool isPrime(int n) { if (n 1) return false; if (n 2) return true; if (n % 2 0) return false; for (int i 3; i * i n; i 2) { if (n % i 0) { return false; } } return true; }3.2 埃氏筛实现vectorint sieveOfEratosthenes(int limit) { vectorbool isPrime(limit 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i limit; i) { if (isPrime[i]) { for (int j i * i; j limit; j i) { isPrime[j] false; } } } vectorint primes; for (int i 2; i limit; i) { if (isPrime[i]) { primes.push_back(i); } } return primes; }3.3 C特有优化内存预分配vector预先reserve足够空间避免多次扩容编译器优化使用-O2或-O3优化级别内联汇编对关键循环可以使用内联汇编进一步优化4. Python实现方案4.1 基础质数判断def is_prime(n): if n 1: return False if n 2: return True if n % 2 0: return False for i in range(3, int(n**0.5) 1, 2): if n % i 0: return False return True4.2 埃氏筛实现def sieve_of_eratosthenes(limit): is_prime [True] * (limit 1) is_prime[0] is_prime[1] False for i in range(2, int(limit**0.5) 1): if is_prime[i]: for j in range(i*i, limit1, i): is_prime[j] False primes [i for i, prime in enumerate(is_prime) if prime] return primes4.3 Python特有优化使用numpy对于大数据量使用numpy数组可以显著提高性能生成器表达式处理大范围时使用生成器节省内存缓存结果使用functools.lru_cache缓存计算结果5. 常见问题与调试技巧5.1 边界条件处理0和1它们既不是质数也不是合数负数题目通常要求处理正整数大数处理注意数据类型的范围限制5.2 性能问题排查无限循环确保循环终止条件正确数组越界筛法时注意数组大小类型溢出大数计算时使用long或BigInteger5.3 测试用例设计好的测试用例应该包含小质数2, 3, 5小合数4, 6, 8边界值0, 1, 最大允许值平方数9, 16, 25大质数如1047296. 面试准备建议掌握基础算法除了埃氏筛还要了解欧拉筛等更高效的算法复杂度分析能清晰解释算法的时间和空间复杂度代码风格注重变量命名、函数拆分和注释沟通能力在编码过程中解释自己的思路异常处理考虑输入验证和错误处理在实际面试中这类题目往往只是起点面试官可能会基于你的解决方案进行扩展提问比如如何优化内存使用如何处理极大范围的质数生成如何将算法并行化我建议在准备阶段不仅要写出正确的代码还要思考这些可能的扩展问题准备好相应的解决方案。在蚂蚁这类顶级互联网公司的面试中单纯正确但平庸的解决方案往往不够需要展现出对问题的深入理解和优化能力。