Dig Deeper
Generator Fun
Generator Fun
The key of this approach is to not store the elements you do not need.
This is a code representation:
from itertools import islice, count
def prime(number):
if number == 0:
raise ValueError('there is no zeroth prime')
gen = islice(filter(lambda counter: all(counter % test != 0 for test in range(2, int(counter ** 0.5) + 1)), count(2)), number)
for _ in range(number - 1): next(gen)
return next(gen)
Let’s dissect it! itertools.count is like range without un upper bound - calling it returns a generator, and for ... in count_obj will result in an infinite loop.
Using a lambda expression, we filter out any numbers above two that are prime.
Doesn’t this result in an infinite loop?
No - filter also returns a generator object (which are evaluated lazily), so while it’s too will produce values infinitely if evaluated, it doesn’t hang to program at the time of instantiation.
itertools.islice takes in a generator object and an end count, returning a generator object which only evaluates until that end count.
The next line exhausts all the values in the generator except the end, and we finally return the last element.
We can utilize the functools.cache decorator for greater speeds at higher values of number, so we take it out.
The added bonus is that a very long line of code is cleaned up.
from itertools import islice, count
from functools import cache
@cache
def is_prime(counter):
return all(counter % test != 0 for test in range(2, int(counter ** 0.5) + 1))
def prime(number):
if number == 0:
raise ValueError('there is no zeroth prime')
gen = islice(filter(is_prime, count(2)), number)
for _ in range(number - 1): next(gen)
return next(gen)
Note that this that not create a list anywhere, and thus is both memory and time efficient.
Read more on itertools on the Python docs.
Tracking
Tracking
This approach includes building a list of all the previous primes until it reaches the nth number, after which it quits the loop and return the last number in the list.
def prime(number):
if number == 0:
raise ValueError('there is no zeroth prime')
counter = 2
primes = [2]
while len(primes) < number:
counter += 1
if all(counter % test != 0 for test in range(2, counter)):
primes.append(counter)
return primes[-1]
Efficiency can be improved slightly by reducing the factor check to the square root of the number…
...
if all(counter % test != 0 for test in range(2, int(counter ** 0.5) + 1)):
...
… or even better, checking whether a new number is merely not divisible by any of the primes (in which case it’s a prime itself):
...
if all(counter % test != 0 for test in primes):
...
Instead of building the list, it’s more memory efficient to just save the number of primes found until now, and return the currently stored number when the nth prime is found.
However, this elongates the code.
def prime(number):
if number == 0:
raise ValueError('there is no zeroth prime')
counter = 2
prime_count = 0
while True:
isprime = True
for test in range(2, int(counter ** 0.5) + 1):
if counter % test == 0:
isprime = False
break
if isprime:
prime_count += 1
if prime_count == number:
return counter
counter += 1
Tip: you can use `for... else` to make your code more idiomatic here.
```python
...
for test in range(2, int(counter ** 0.5) + 1):
if counter % test == 0:
break
else:
prime_count += 1
if prime_count == number:
return counter
```
The else block is executed if the `for` loop completes normally - that is, without `break`ing.
Read more on [for/else][for-else]
Source: Exercism python/nth-prime