How does this if all statement work? Euler 7

Question

I was looking at the code below and I can't seem to get my head around line 6 with the if all statement. Could someone explain what it is doing and what happens in the first iteration when the list is empty. This is from Euler 7

def main():
    number_prime_to_find = 1001
    x = 2
    list_of_primes = []
    while (len(list_of_primes) < number_prime_to_find):
        if all(x % prime for prime in list_of_primes):
            list_of_primes.append(x)

I'm sure I have seen this exact question on SO. Have you searched it before posting it here? — mad_, May 24 '20 at 01:52
```%``` refers to the residual of the division between two numbers. So line 6 basically checks if the residual of ```x``` and a ```prime``` number is different of 0, if passes this test for all the prime numbers in ```list_of_primes``` then ```x``` must be a prime and therefore appended to ```list_of_primes``` — EnriqueBet, May 24 '20 at 01:54
In the first iteration, list_of_primes is empty, so that list comprehension returns another empty list. So the term becomes `all([]) `, which is True — SimonR, May 24 '20 at 01:56

paxdiablo · Answer 1 · 2020-05-24T02:55:36.313

The block:

if all(x % prime for prime in list_of_primes):
    list_of_primes.append(x)

means "check that, for all primes in the list, x is not a multiple of that prime". It's effectively the same as (pseudo-code):

xIsAPrime = True
for each prime in list_of_primes:
    if x % prime == 0:
        xIsAPrime = False
        break
if xIsAPrime:
    list_of_primes.append(x)

If a candidate prime is not a multiple of any primes in the list, then that candidate prime is an actual prime, so is added to the list.

If the list of primes is empty (initial state), then the first number you check will be considered a prime (you're starting at 2 so that's correct).

The reason for this is that all(x) simply means "true if there are no falsey values in the iterable x, false otherwise". Since an empty iterable cannot have falsey values by definition, performing all() on it will always give true.

Following that (the addition of 2 to the list):

The next prime will then be the next number that's not a multiple of two, so we add 3;
The next prime after that will be the next number that's not a multiple of two or three, so we add 5;
The next prime after that will be the next number that's not a multiple of any in the set { 2, 3, 5 }, hence we add 7;
The next prime after that will be the next number that's not a multiple of any in the set { 2, 3, 5, 7 }, add 11;
And so on, until the list size gets big enought that the final item is the prime we want.

Unfortunately for you, that bit of code doesn't seem to ever change x (unless you've just left it off in the question) so it's unlikely to give you what you want, especially since you also don't seem to print or return it. You can rectify that with:

def main():
    number_prime_to_find = 1001
    list_of_primes = []
    x = 2
    while len(list_of_primes) < number_prime_to_find:
        if all(x % prime for prime in list_of_primes):
            list_of_primes.append(x)
        x += 1                  # Need to modify x
    return list_of_primes[-1]   # Probably also want to output it.

print(main())

As an aside, you could further optimise this by realising that, other then two and three, all primes are of the form 6n ± 1, for n > 0 (see here for a more detailed explanation as to why this is the case):

def main():
    number_prime_to_find = 1001
    list_of_primes = [2, 3]
    (x, xadd) = (5, 2)
    while len(list_of_primes) < number_prime_to_find:
        if all(x % prime for prime in list_of_primes):
            list_of_primes.append(x)
        x += xadd          # Skip impossible primes.
        xadd = 6 - xadd    # Alternate adding 2, 4: gives 7, 11, 13, 17, ...
    return list_of_primes[-1]

print(main())

This is likely to be about (very roughly) three times faster, since you only need to check two candidates in each group of six numbers, rather than the original six candidates.

You may also want to consider making it a more generic function. While finding the 1001st prime is something we all want to do three or four times a day, you may want to avoid having to write a whole other function should some new starter on the team decide they want to get the 1002nd :-)

Something like this, I would imagine:

def getNthPrime(n):
    # Cater for smart-alecs :-)

    if n < 1: return None

    # Initial list holds those that aren't 6n +/- 1.

    primeList = [2, 3]

     # Next candidate and candidate increment.

    (candidate, delta) = (5, 2)

    # Until we have enough primes in list.

    while len(primeList) < n:
        # Add to list if it's prime, move to next candidate.

        if all(candidate % prime for prime in primeList):
            primeList.append(candidate)
        candidate += delta
        delta = 6 - delta

    # List big enough, return correct one. Note we use n-1 here
    # rather than -1, since you may want prime #1 and the list
    # STARTS with two primes. We subtract one because first prime
    # is actually at index zero.

    return primeList[n-1] 

print(getNthPrime(1001))

How does this if all statement work? Euler 7

1 Answers1