go语言中对`uint64`执行左移操作时,若位移量≥64,结果恒为0,导致位图筛法在处理大于63的数字时完全失效;本文详解其原理,并提供适用于project euler #3(求600851475143最大质因数)的健壮解决方案。
在Go中,位移操作符 > 的行为由语言规范严格定义:当右操作数(位移量)大于或等于目标整数类型的位宽时,结果未定义(实际实现中为0)。对于 uint64 类型(64位),1
你的 primeset 函数试图用单个 uint64 变量作为“位图”标记 [2, n] 范围内的合数,但 n = 100 时需索引到第100位,远超 uint64 的容量。此时 primes |= (1 质数判定严重错误。
✅ 正确做法:避免越界位图,改用高效质因数分解
Project Euler #3 的核心并非生成全部质数,而是分解给定大整数并找出最大质因数。直接筛法(尤其位图)在此场景下既低效又不适用。推荐采用 试除法优化版:从小到大枚举可能因子,边除边更新,时间复杂度仅为 O(√n),且内存恒定。
以下是修正后的完整可运行代码: