miller-rabin 多线程 python代码

以下是使用 Python 代码实现的基于 Miller-Rabin 算法的多线程判断素数的示例：

import threading
import math

# 判断是否为素数
def is_prime(n, k):
    if n <= 1 or (n > 2 and n % 2 == 0):
        return False
    d = n - 1
    while d % 2 == 0:
        if pow(k, d // 2, n) == n - 1:
            return True
        d //= 2
    x = pow(k, d, n)
    return x == 1 or x == n - 1

# 多线程判断素数
def parallel_is_prime(n, k, start, end, results, lock):
    for i in range(start, end + 1):
        if not is_prime(i, k):
            with lock:
                results[i] = False
            return
    with lock:
        for i in range(start, end + 1):
            results[i] = True

# 主函数
if __name__ == "__main__":
    n = 1000000 # 需要判断的数
    k = 2 # 判断素数的基数
    num_threads = 4 # 线程数
    results = [False] * (n + 1) # 判断结果
    lock = threading.Lock() # 互斥锁
    threads = [] # 线程数组
    block_size = n // num_threads # 每个线程处理的块大小
    for i in range(num_threads):
        start = i * block_size + 1
        end = n if i == num_threads - 1 else (i + 1) * block_size
        t = threading.Thread(target=parallel_is_prime, args=(n, k, start, end, results, lock))
        threads.append(t)
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    is_all_prime = all(results[1:]) # 判断所有数是否都是素数
    if is_all_prime:
        print(n, "is a prime number.")
    else:
        print(n, "is not a prime number.")

在这个示例代码中，我们首先定义了一个 `is_prime` 函数来判断一个数是否为素数，该函数采用 Miller-Rabin 算法进行判断。接下来，我们定义了一个 `parallel_is_prime` 函数，用于在一个线程内判断一段范围内的数是否为素数。这个函数的参数包括需要判断的数 n、判断素数的基数 k、该线程处理的起始位置和结束位置、判断结果 results 和互斥锁 lock。在函数内部，我们首先对该范围内的每个数进行判断，如果发现某个数不是素数，则可以直接将该数的判断结果设置为 False，并退出该线程的运行。如果该范围内的所有数都是素数，则将这些数的判断结果设置为 True。最后，我们在主函数中创建多个线程来并发地判断素数，并在所有线程运行完毕后，将结果进行合并。如果所有数都是素数，则说明该数是素数，否则，该数为合数。