Python如何遍历指定数的非更小倍数的倍数？及埃氏筛效率疑问

当然可以实现。你要遍历的是指定数k与大于等于k的质数的乘积——这类数的因数仅包含1、k、对应质数及乘积本身，不会被任何小于k的数（除1外）整除。

实现示例 #

可以用生成器动态生成目标数，结合质数判断逻辑：

def multiples_of_k_without_small_divisors(k: int):
    if k < 2:
        raise ValueError("k必须大于等于2")
    # 先返回k的平方（k*k）
    yield k * k
    # 生成大于k的质数，逐个与k相乘
    num = k + 1
    while True:
        is_prime = True
        # 质数判断：检查到平方根即可
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            yield k * num
        num += 1

# 测试：获取k=13的前5个结果
gen = multiples_of_k_without_small_divisors(13)
for _ in range(5):
    print(next(gen))
# 输出：169 221 247 299 377

如果需要处理大数，建议替换掉简单的质数判断，改用高效的质数生成方法（如分段筛），避免性能瓶颈。

你的代码在n=9×10⁹时性能暴增，核心原因如下：

1. 超大数组引发的内存溢出与磁盘交换
   np.ones(n+1, dtype=bool)会创建一个包含90亿+1个元素的数组，numpy的bool类型每个元素占1字节，总内存占用约9GB。若机器物理内存不足，操作系统会将部分数组数据交换到磁盘（swap），磁盘读写速度比内存慢数千倍，直接导致所有数组操作耗时剧增。

2. 非连续内存访问的缓存命中率暴跌
   执行primes[i**2::2*i] = False时，随着i增大，步长2*i也会变大，被修改的元素在内存中是分散的非连续地址。CPU缓存专为连续内存访问优化，非连续访问会触发大量缓存miss，每次操作都要从主存（甚至磁盘）读取数据，耗时随步长增大呈指数级上升——这就是你观察到的“i越大耗时越多”的关键原因。

你提到的“重复设置已为False的元素”对性能影响极小，numpy赋值操作覆盖已有值的开销可以忽略，不是主要瓶颈。

优化建议 #

• 改用分段筛法（Segmented Sieve）：不需要一次性创建整个大数组，分块处理区间，大幅降低内存占用。
• 放弃numpy大数组操作：改用原生Python结合内存高效的数据结构（如bitset、整数位运算模拟位集合），更灵活控制内存访问模式，适配超大n的场景。

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