Python多线程统计300万范围内素数：代码报错与性能优化求助

原始代码的核心问题 #

• 区间划分错误：变量名devision和division混用，初始division为0，导致Thread 0的统计区间为空，返回0个素数。
• 多线程逻辑失效：主线程提前同步计算素数，线程传递的参数无效，且未定义out变量，线程未执行实际统计任务。
• 素数判断算法低效：遍历范围到i/2，未排除偶数，计算量过大导致运行极慢甚至被系统终止。

修正优化后的代码 #

import threading
import math

Nthreads = 4
maxNumber = 3000000
# 共享结果容器，加锁保证线程安全
prime_counts = []
lock = threading.Lock()

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    # 直接排除偶数
    if n % 2 == 0:
        return False
    # 仅遍历奇数到sqrt(n)，大幅减少计算量
    sqrt_n = int(math.sqrt(n)) + 1
    for j in range(3, sqrt_n, 2):
        if n % j == 0:
            return False
    return True

def count_primes(start, end):
    count = 0
    for num in range(start, end):
        if is_prime(num):
            count += 1
    # 加锁写入结果，避免线程冲突
    with lock:
        prime_counts.append(count)
    print(f"Thread {threading.current_thread().name} 完成统计，素数数量：{count}")

def main():
    interval = maxNumber // Nthreads
    threads = []
    
    for i in range(Nthreads):
        start = i * interval
        # 最后一个线程覆盖剩余数值，避免遗漏
        end = (i + 1) * interval if i != Nthreads - 1 else maxNumber
        # 跳过0和1，减少无效计算
        if start < 2:
            start = 2
        # 创建并启动线程
        thread = threading.Thread(target=count_primes, args=(start, end), name=str(i))
        threads.append(thread)
        thread.start()
    
    # 等待所有线程执行完毕
    for thread in threads:
        thread.join()
    
    total = sum(prime_counts)
    print(f"\n3000000以内总素数数量：{total}")

if __name__ == "__main__":
    main()

关键优化说明 #

1. 正确的区间划分：
   • 按线程数平均划分区间，最后一个线程处理剩余数值，避免遗漏。
   • 直接跳过0和1，减少无效判断。
2. 高效素数判断：
   • 提前排除偶数和小于等于1的数，减少一半以上的循环次数。
   • 仅遍历到sqrt(n)而非n/2，计算量骤减。
3. 正确的多线程实现：
   • 使用线程锁保证共享结果容器的线程安全，避免数据冲突。
   • 每个线程独立负责一个区间的统计，真正利用多线程并行处理。
4. 性能提升：优化后的算法效率比原代码提升数倍，能快速完成3000000以内的素数统计，不会出现被系统终止的情况。

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