Проверка на простоту

Проверка на простоту определяет, делится ли число только на 1 и само себя. Достаточно перебрать возможные делители до sqrt(n): если делителя там нет, число простое, так как делители идут парами относительно корня.

Сложность: время O(sqrt(n)); память: O(1). Для очень больших чисел применяют вероятностные тесты (Миллера-Рабина).

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

print([x for x in range(2, 20) if is_prime(x)])  # [2,3,5,7,11,13,17,19]