2
\$\begingroup\$

I have a prime function which accepts a list of numbers and checks if all of the numbers in the list are prime.

Here is my code:

from math import sqrt
def primes(lista):
    return all(True if n == 2 else bool(all(n % x for x in list(range(3, int(sqrt(n)+1), 2))+ [2])) for n in lista)

Can I make this code more readable without making the actual function slower?

\$\endgroup\$
  • \$\begingroup\$ Like this? \$\endgroup\$ – Mast Jun 7 '18 at 9:42
  • 1
    \$\begingroup\$ To answer this well we really need to know the intended usage: will lista be small or large, will its elements be small or large, and if the answers are respectively small and large, will the elements be contained in a small range? \$\endgroup\$ – Peter Taylor Jun 7 '18 at 9:52
  • \$\begingroup\$ Also, does lista contain multiple elements? \$\endgroup\$ – Graipher Jun 7 '18 at 9:59
  • \$\begingroup\$ lista can contain 1 or more elements, and lista will usually be large, about 100 - 200 elements in lista. \$\endgroup\$ – A................... Jun 7 '18 at 14:18
10
\$\begingroup\$

There are a few obvious improvements, which either make it more readable or even faster:

  • True if n == 2 else ... is equivalent to n == 2 or ...
  • bool(all(...)) is the same as all()
  • You could pull out the special case of 2 in all(n % x for x in list(range(3, int(sqrt(n)+1), 2))+ [2]) by doing (n % 2 and all(n % x for x in range(3, int(sqrt(n)+1), 2))). This has the advantage that the range does not get consumed into a list which makes this stop generating values as soon as a value is found not to be prime.

This gives:

from math import sqrt

def primes(lista):
    return all(n == 2 or (n % 2 and all(n % x for x in range(3, int(sqrt(n)+1), 2))) for n in lista)

But if you really want to make it more readable, you should factor out the prime check into another function:

from math import sqrt

def is_prime(n):
    """Check if `n` is prime.

    Uses exhaustive search to look for factors up to sqrt(n) + 1.
    """
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    return all(n % x for x in range(3, int(sqrt(n) + 1), 2))


def all_primes(lista):
    """Check if all numbers in `lista` are primes."""
    return all(is_prime(n) for n in lista)

Another alternative is to compute a set of primes once and then just check if all of them are in this set:

primes_set = set(prime_sieve(100000))

def all_primes_set(lista):
    lista_set = set(lista)
    return len(primes_set & lista_set) == len(lista_set)

On my machine all of these are faster than your original function:

primes_list = list(prime_sieve(100000))

%timeit primes_op(primes_list)
77.3 ms ± 373 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit primes(primes_list)
67.8 ms ± 706 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit all_primes(primes_list)
70.9 ms ± 235 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit all_primes_set(primes_list)
823 µs ± 9.53 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

So if you know what the largest number is which you need to check, checking against a set that is computed only once is the fastest.

\$\endgroup\$
  • \$\begingroup\$ I apologize for intrude in here, but what if the list of primes to check has more than 100000 numbers, does it return false? Just curious and don't know Python. EDIT Nevermind, failed to read the retrun condition. \$\endgroup\$ – auhmaan Jun 7 '18 at 15:28
  • \$\begingroup\$ I never understand why people special-case 2 when checking for primality. Why 2? Who not 3? Why not 31? There’s absolutely nothing special about 2 as a prime (apart from being the first, but by induction then we should also special case 3, after checking for 2. And then 5, after checking for 3. … aaand we’ve reinvented the sieve.) \$\endgroup\$ – Konrad Rudolph Jun 7 '18 at 17:51
  • \$\begingroup\$ @KonradRudolph it is the only even prime, so you can go in steps of 2 afterwards \$\endgroup\$ – Graipher Jun 7 '18 at 17:52
  • \$\begingroup\$ @Graipher And after checking for 3 we can go up in steps of 3 (and check the n and n+1). Again, this is just the beginning of the sieve. \$\endgroup\$ – Konrad Rudolph Jun 7 '18 at 17:53
  • \$\begingroup\$ @auhmaan I just chose a number that is probably larger than the largest number in lista. \$\endgroup\$ – Graipher Jun 7 '18 at 17:53
5
\$\begingroup\$

for each number in lista, you iterate over the range(3, int(sqrt(n)+1), 2). You even unnecessarily instantiate this range to a list.

You have 2 alternatives.

  1. You test each element in lista with a faster prime tester
  2. You generate all primes to max(lista), and then check whether all elements from lista are in those primes

Which of the 2 options is better depends on lista. If there are a lot, smaller elements, the 2nd method is faster, for a few, larger elements, method 1 will be better.

I will not get into details on which method to generate all the primes to max(lista), or the prime check. Here you can choose the algorithm most suited for your need. There are a lot alternative on the web and SO.

method 1

This is basically what you did, but with an inline, slow check for primes

def isprime(x):
    pass # choose your test

def test_primes(lista):
    return all(isprime(x) for x in lista)

This can be rewritten with map

def test_primes(lista):
    return all(map(isprime, lista))

Whichever of these 2 is best depends mainly on preference

method 2:

def get_primes_to(x):
    pass

def test_primes(lista):
    max_a = max(lista)
    primes = set(get_primes_to(max_a))
    return all(i in primes for i in lista)

method 2b

Checking whether all elements of lista are primes can also be done with set.issubset

def test_primes(lista):
    max_a = max(lista)
    primes = set(get_primes_to(max_a))
    return set(lista) <= primes
\$\endgroup\$
  • \$\begingroup\$ Method 2b requires no intermediary set object for lista because set.issuperset() accepts arbitrary iterables: primes.issuperset(lista). The implemented algorithm should be similar to the generator expression in method 2a. \$\endgroup\$ – David Foerster Jun 7 '18 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.