Create a python code that counts prime numbers in range(3000000) using for-looped multithreading(e.g-CodePudding

I'm trying to run this program but it is showing me "Thread 0 has 0 prime numbers" in the console followed by "Killed" after 5 minutes. Moreover, it is very slow. Please help me develop and correct this code.

import time
Nthreads=4
maxNumber=3000000
starting_range=0 
ending_range=0
division=0
lst=[]

def prime(x, y):
    prime_list = []
    for i in range(x, y):
        if i == 0 or i == 1:
            continue
        else:
            for j in range(2, int(i/2) 1):
                if i % j == 0:
                    break
            else:
                prime_list.append(i)
    return prime_list
  


def func_thread(x, y):
    out.append(prime(x, y))

thread_list = []

results = len(lst)
for i in range(Nthreads):
        devision=maxNumber//Nthreads
        starting_range = (i-1)*division 1
        ending_range = i*devision
        lst = prime(starting_range, ending_range)
        print(" Thread ", i, " has ", len(lst), " prime numbers." )
        thread = threading.Thread(target=func_thread, args=(i, results))
        thread_list.append(thread)
for thread in thread_list:
 thread.start()
for thread in thread_list:
 thread.join()```

CodePudding user response：

In Python, if you use multithreading for CPU-bound tasks, it will be slower than if you don't use multithreading. You need to use multiprocessing for this problem. You can read this article for more informations: https://www.geeksforgeeks.org/difference-between-multithreading-vs-multiprocessing-in-python/

CodePudding user response：

Multithreading is wholly inappropriate for CPU-intensive work such as this. However, it can be done:

from concurrent.futures import ThreadPoolExecutor

NTHREADS = 4
MAXNUMBER = 3_000_000
CHUNK = MAXNUMBER // NTHREADS
assert MAXNUMBER % NTHREADS == 0
RANGES = [(base, base CHUNK) for base in range(0, MAXNUMBER, CHUNK)]

all_primes = []

def isprime(n):
    if n <= 3:
        return n > 1
    if not n % 2 or not n % 3:
        return False
    for i in range(5, int(n**0.5) 1, 6):
        if not n % i or not n % (i   2):
            return False
    return True

def process(_range):
    lo, hi = _range
    if lo < 3:
        all_primes.append(2)
        lo = 3
    elif lo % 2 == 0:
        lo  = 1
    for p in range(lo, hi, 2):
        if isprime(p):
            all_primes.append(p)

with ThreadPoolExecutor() as executor:
    executor.map(process, RANGES)

The all_primes list is unordered. Note also that this strategy will only work if MAXNUMBER is exactly divisible by NTHREADS.

Note on performance:

This takes 7.88s on my machine. A multiprocessing variant takes 2.90s