```
def primes(number):
not_prime = set()
primes = []
for num in range(2, number+1):
if num not in not_prime:
primes.append(num)
not_prime.update(range(num*num, number+1, num))
return primes
```

This is the fastest method so far tested, at all input sizes.

With only a single loop, performance scales linearly: `O(n)`

.

A key step is the set `update()`

.

Less commonly seen than `add()`

, which takes single element, `update()`

takes any iterator of hashable values as its parameter and efficiently adds all the elements in a single operation.

In this case, the iterator is a range resolving to all multiples, up to the limit, of the prime we just found.

Primes are collected in a list, in ascending order, so there is no need for a separate sort operation at the end.

```
def primes(number):
numbers = set(item for item in range(2, number+1))
not_prime = set(not_prime for item in range(2, number+1)
for not_prime in range(item**2, number+1, item))
return sorted(list((numbers - not_prime)))
```

After a set comprehension in place of an explicit loop, the second example uses set-subtraction as a key feature in the return statement.

The resulting set needs to be converted to a list then sorted, which adds some overhead, scaling as O(n *log* n).

In performance testing, this code is about 4x slower than the first example, but still scales as `O(n)`

.

```
def primes(number: int) -> list[int]:
start = set(range(2, number + 1))
return sorted(start - {m for n in start for m in range(2 * n, number + 1, n)})
```

The third example is quite similar to the second, just moving the comprehension into the return statement.

Performance is very similar between examples 2 and 3 at all input values.

### Sets: strengths and weaknesses

Sets offer two main benefits which can be useful in this exercise:

- Entries are guaranteed to be unique.
- Determining whether the set contains a given value is a fast, constant-time operation.

Less positively:

- The exercise specification requires a list to be returned, which may involve a conversion.
- Sets have no guaranteed ordering, so two of the above examples incur the time penalty of sorting a list at the end.