[SOLVED] Most efficient way to filter prime numbers from a list of random numbers in Python

Issue

I have a list filled with random numbers and I want to return the prime numbers from this list. So I created these functions:

def is_prime(number):
    for i in range(2, int(sqrt(number)) + 1):
        if number % i == 0:
            return False

    return number > 1

And

def filter_primes(general_list):
    return set(filter(is_prime, general_list))

But I want to improve performance, so how can I achieve this?

Solution

Sieve of Eratosthenes, taking about 0.17 seconds for primes under 10 million on PyPy 3.5 on my device:

from array import array

def primes(upper):
    numbers = array('B', [1]) * (upper + 1)

    for i in range(2, int(upper ** 0.5) + 1):
        if numbers[i]:
            low_multiple = i * i
            numbers[low_multiple:upper + 1:i] = array('B', [0]) * ((upper - low_multiple) // i + 1)

    return {i for i, x in enumerate(numbers) if i >= 2 and x}

and the filter function:

filter_primes = primes(10_000_000).intersection

Answered By – Ry-

Answer Checked By – Senaida (BugsFixing Volunteer)