Как эффективно проверить число на простоту?

Главная оптимизация: проверять делители только до корня из n, а не до n. Если у числа есть делитель больше корня, то парный ему делитель меньше корня — так что искать выше корня бессмысленно.

def is_prime(n):
    if n < 2:
        return False
    if n < 4:
        return True          # 2 и 3
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:         # до корня из n
        if n % i == 0:
            return False
        i += 2               # только нечётные
    return True

Это O(√n) вместо O(n). Для проверки одного числа более чем достаточно. Если надо найти ВСЕ простые до N — бери решето Эратосфена, оно ещё эффективнее.