Wheel筛法剔除操作技术在无预剔除代码中的实现问询

一、primes235中ndxs数组与除以30的核心逻辑 #

首先得明白，30是2×3×5的乘积——这是235轮筛法的基础周期。所有大于5的素数，必然符合30k + r的形式，其中r是与30互质的数：1、7、11、13、17、19、23、29，共8个，这8个值就是wheel的核心元素。

• 除以30的作用：把任意大于5的数映射到30的周期内，通过取余n%30得到对应的r，快速判断这个数是否在wheel的候选集中（只有在候选集中的数才有资格成为素数）。
• ndxs数组的作用：本质是个索引映射表。比如wheel列表是[1,7,11,13,17,19,23,29]，ndxs数组的索引是0到29的余数，值是该余数在wheel中的位置（比如ndxs[7] = 1，ndxs[11] = 2）。这样不用每次遍历wheel找位置，直接通过余数查索引，大幅提升查找效率。

举个实际场景：当处理素数p时，先算p%30得到余数，用ndxs直接拿到它在wheel中的位置，再基于这个位置计算它的倍数在筛中的偏移，避免重复计算。

二、Willy Good提到的技术落地方案 #

1. 用数组存储间隙/标记替代列表 #

Python列表是动态容器，内存布局不连续，CPU缓存命中率低。换成紧凑的数组类型（比如array.array或bytearray）能减少内存开销，提升访问速度：

• 把筛的标记位从列表改成bytearray，每个元素用1字节存0/1（标记是否为素数），比列表的每个元素占28字节（Python int对象）节省大量内存。
• 如果存wheel间隙，用array.array('I')（无符号整数）存储，内存连续，遍历和运算更快。

2. 利用现代CPU高效处理整数乘加 #

现代CPU对整数乘加指令的吞吐量远高于除法、取模这类复杂操作，优化时要尽量替换：

• 计算素数倍数时，用current += p的累加方式替代p*k的乘法（虽然底层都是乘加，但累加更贴合CPU流水线）。
• 结合wheel周期，预计算每个候选数在wheel中的偏移量，用乘加直接定位下一个要标记的位置，避免频繁取模。比如预计算wheel中每个位置与素数p的乘积对应的余数，用这个余数的索引偏移来快速更新筛的标记位。

3. 预剔除+W4轮优化 #

• 预剔除：先直接返回小于等于5的素数，初始化筛时直接排除2、3、5的所有倍数，只保留wheel中的8个候选数对应的位置，减少后续筛的工作量。
• W4轮优化：把235轮（周期30）升级为W4轮（周期210，即2×3×5×7的乘积），与210互质的数有48个，更大的周期意味着每个周期内需要处理的候选数比例更低，进一步减少筛的次数。实现时只需把wheel扩展为210的互质余数列表，ndxs数组扩容到210即可。

优化后的代码示例 #

import array

def primes235_optimized(limit):
    if limit < 2:
        return []
    # 预定义小素数，直接返回
    small_primes = [2, 3, 5]
    if limit < 7:
        return [p for p in small_primes if p <= limit]
    
    # 235轮的候选余数
    wheel = [1, 7, 11, 13, 17, 19, 23, 29]
    wheel_len = len(wheel)
    # 构建余数到wheel索引的映射数组
    ndxs = array.array('B', [0] * 30)
    for idx, r in enumerate(wheel):
        ndxs[r] = idx
    
    # 计算筛的总长度：每个周期对应wheel_len个位置
    total_cycles = (limit - 1) // 30 + 1
    sieve = bytearray([1]) * (total_cycles * wheel_len)
    sieve[0] = 0  # 1不是素数
    
    max_sqrt = int(limit ** 0.5)
    for cycle in range(total_cycles):
        for idx in range(wheel_len):
            num = cycle * 30 + wheel[idx]
            if num > max_sqrt:
                break
            if sieve[cycle * wheel_len + idx]:
                # 拿到当前素数在wheel中的索引
                p_idx = ndxs[num % 30]
                # 计算素数平方的起始位置（筛的起始点）
                start_num = num * num
                start_cycle = start_num // 30
                start_r = start_num % 30
                start_pos = start_cycle * wheel_len + ndxs[start_r]
                # 预计算步长：当前素数与wheel每个元素乘积的索引偏移
                step = []
                for r in wheel:
                    product_r = (num * r) % 30
                    step.append(ndxs[product_r] - p_idx)
                # 用累加标记倍数，避免重复计算
                current_pos = start_pos
                while current_pos < len(sieve):
                    sieve[current_pos] = 0
                    current_pos += num * wheel_len + step[p_idx]
    
    # 收集所有素数
    primes = small_primes.copy()
    for cycle in range(total_cycles):
        for idx in range(wheel_len):
            num = cycle * 30 + wheel[idx]
            if num > limit:
                break
            if sieve[cycle * wheel_len + idx]:
                primes.append(num)
    return primes

内容的提问来源于stack exchange，提问作者Kevin Perez