parallel-eratosthenes.py

import math
import sys   # stackoverflow.com/questions/49149932/
             #     python-generator-and-setgenerator-get-different-results
             # by stackoverflow.com/users/4658633/blaise-wang

import time
from mpi4py import MPI

import eratosthenes

comm = MPI.COMM_WORLD
rank = comm.Get_rank()
size = comm.Get_size()

TAG_RESULT = 0

n = sys.argv[1]
if n.isdigit():
    start_time = time.time()
    n = int(n)
    sqrt_n = int(math.sqrt(n))

    task_per_block = int(math.ceil((n - 1) / size))
    begin = 2 + rank * task_per_block
    end = begin + task_per_block if begin + task_per_block <= n + 1 else n + 1
    if rank == 0:
        begin = sqrt_n if sqrt_n < end else begin
    sieve_list = [True] * (end - begin)
    prime_list = eratosthenes.sieve(sqrt_n)

    if rank == 0:
        result = sum(prime_list)
        for prime in prime_list:
            start = begin if begin % prime == 0 else (int(begin / prime) + 1) * prime
            for multiple in range(start, end, prime):
                sieve_list[multiple - begin] = False
        result += sum(i + begin for i, v in enumerate(sieve_list) if v)
        result_received = 0
        while result_received < size - 1:
            data = comm.recv(source=MPI.ANY_SOURCE, tag=TAG_RESULT)
            result += data
            result_received += 1
        print(result)
        print(time.time() - start_time)
    else:
        for prime in prime_list:
            start = begin if begin % prime == 0 else (int(begin / prime) + 1) * prime
            for multiple in range(start, end, prime):
                sieve_list[multiple - begin] = False
        result = sum(i + begin for i, v in enumerate(sieve_list) if v)
        comm.send(result, dest=0, tag=TAG_RESULT)

their previous code from TIO:

import math

n = 1000


def candidate_range(limit):
    value = 5
    increment = 2
    while value < limit + 1:
        yield value
        value += increment
        increment ^= 6


def sieve(limit):
    prime_list = [2, 3]
    sieve_list = [True] * (limit + 1)
    for each_number in candidate_range(limit):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number * each_number, limit + 1, each_number):
                sieve_list[multiple] = False
    return prime_list


def yield_multiple(end: int):
    for prime in sieve(int(math.sqrt(end))):
        for multiple in range(prime + prime, end, prime):
            yield multiple


result = [2, 3] + [v for v in candidate_range(n) if v not in yield_multiple(n)]
print(len(result))