如何在Julia中实现更高效的素数列表生成方法

原代码性能瓶颈 #

你的代码性能差的核心原因不是拆分为两个函数，而是逻辑本身存在大量冗余：

• 素数判断逻辑冗余：prime_check 函数只要检测到任意一个可整除的因子就能判定非素数，无需遍历完所有2~n-1的数，也不需要额外创建trash、primes数组存储中间结果，直接返回布尔值即可
• 因子遍历范围过大：判断n是否为素数只需要遍历到√n即可，若√n以内没有因子，更大的数也不可能成为n的因子
• 重复计算浪费：prime_list中对同一个i调用了两次prime_check，重复执行了素数判断逻辑
• 算法选择不合理：求n以内所有素数的场景下，埃拉托斯特尼筛法的效率远高于逐个判断每个数是否为素数

优化实现 #

基础优化版（基于原逻辑调整为单函数） #

在原有逐个判断的逻辑上优化冗余点，性能提升明显：

function prime_list(n)
    n < 2 && return Int[]
    primes = Int[]
    for i in 2:n
        is_prime = true
        # 仅遍历到i的平方根即可完成素数判断
        for j in 2:isqrt(i)
            if i % j == 0
                is_prime = false
                break # 找到因子直接终止判断，无需继续遍历
            end
        end
        is_prime && push!(primes, i)
    end
    return primes
end

高性能筛法版 #

如果n数值较大，推荐使用埃氏筛实现，时间复杂度仅为O(n log log n)，性能远高于逐个判断的方案：

function prime_list(n)
    n < 2 && return Int[]
    # 初始化布尔标记数组，默认所有数为素数
    is_prime = trues(n)
    is_prime[1] = false
    for i in 2:isqrt(n)
        if is_prime[i]
            # 批量标记i的所有倍数为非素数
            is_prime[i*i:i:n] .= false
        end
    end
    # 收集所有标记为素数的索引，即为结果
    return findall(is_prime)
end

优化效果说明 #

• 原代码时间复杂度约为O(n²)，基础优化版时间复杂度约为O(n√n)，筛法版性能提升最为显著
• 优化后去掉了所有不必要的数组创建、重复计算逻辑，同时显式指定数组为Int类型，符合Julia的性能优化规范，运行效率会有量级提升

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