printing reversed list of prime numbers with given interval

Question

so I figured out how to print all the prime number in reversed form a given interval, but for a test case when they place the lower bound to 1, it will print it as well. As we know that 1 is not a prime number.

my code is:

def prime_list_reversed(x, y):
"""
Input: the number x and y
Output: all prime numbers within [x,y] in reverse order

>>> prime_list_reversed(3, 10)
[7, 5, 3]
>>> prime_list_reversed(3, 3)
[3]
>>> prime_list_reversed(2, 2)
[2]
"""
assert type(x) == int, "first argument must be an integer"
assert type(y) == int, "second argument must be an integer"
assert x > 1, "1 is not a prime number"
assert y >= x,  "second argument must be >= the first one"

# YOUR CODE IS HERE #
lst = []
for i in range(x, y + 1):
    for c in range(2, i):
        if (i % c) == 0:
            break
    else:
        lst.append(i)
return list(reversed(lst))

one test case

prime_list_reversed(1, 3)
[3,2,1]

Answer 1

Your prime checker will for i=1 construct the range(2, 1), but that range is empty. Indeed:

>>> list(range(2, 1))
[]

So that means no checking is done for i=1, and hence your program considers it to be a prime number. There are two things that we can do here:

1. check with the if statement that i == 1 to avoid emitting;
2. ensuring that the outer range can never emit 1 in the first place.

def prime_list_reversed(x, y):
    # ...
    lst = []
    for i in range(max(2, x), y + 1):
        for c in range(2, i):
            if (i % c) == 0:
                break
        else:
            lst.append(i)
    return list(reversed(lst))

The above solves the problem, but it is not very elegantly: we first construct a list, and then reverse the list. We can simply emit elements in reverse as well:

def prime_list_reversed(x, y):
    # ...
    lst = []
    for i in range(y, max(2, x) - 1, -1):
        for c in range(2, i):
            if (i % c) == 0:
                break
        else:
            lst.append(i)
    return lst

Now we thus yield elements in reverse. But still the code is inefficient: we test all even numbers. But it is sufficient to test if a number can be divided by 2, if not, we can omit check for 4, 6, etc. since if it is not divisable by 2, it definitely is not divisable by 4, 6. Instead of checking if a number is divisable by 2

def prime_list_reversed(x, y):
    # ...
    lst = []
    for i in range(y - (~y & 1), max(3, x) - 1, -2):
        for c in range(3, i, 2):
            if (i % c) == 0:
                break
        else:
            lst.append(i)
    if x <= 2 < y:
        lst.append(2)
    return lst

But still it can more efficient. If a number a is divisable by b, we know that there is a c = a/b. This means that if b >√a, then c≤√a. We can exploit this property: it is sufficient to check up to √i, since we know that otherwise we have tested it through the other division:

from math import ceil, sqrt

def prime_list_reversed(x, y):
    # ...
    lst = []
    for i in range(y - (~y & 1), max(3, x) - 1, -2):
        for c in range(3, ceil(sqrt(i))+1, 2):
            if not i % c:
                break
        else:
            lst.append(i)
    if x <= 2 < y:
        lst.append(2)
    return lst

Finally it is usually better to make this a generator, since this allows us to lazily for example take the first 10 elements:

from math import ceil, sqrt

def prime_list_reversed(x, y):
    # ...
    for i in range(y - (~y & 1), max(3, x) - 1, -2):
        for c in range(3, ceil(sqrt(i))+1, 2):
            if not i % c:
                break
        else:
            yield i
    if x <= 2 < y:
        yield 2

we then obtain as for the range between 1 and 500:

>>> list(prime_list_reversed(1, 500))
[499, 491, 487, 479, 467, 463, 461, 457, 449, 443, 439, 433, 431, 421, 419, 409, 401, 397, 389, 383, 379, 373, 367, 359, 353, 349, 347, 337, 331, 317, 313, 311, 307, 293, 283, 281, 277, 271, 269, 263, 257, 251, 241, 239, 233, 229, 227, 223, 211, 199, 197, 193, 191, 181, 179, 173, 167, 163, 157, 151, 149, 139, 137, 131, 127, 113, 109, 107, 103, 101, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2]