Простое число (Is Prime)

Условие:
Дано целое неотрицательное число n. Определите, является ли оно простым. Простое число больше 1 и делится без остатка только на 1 и на само себя. Числа 0 и 1 простыми не считаются.

Входные данные:
Одно целое число n.

Выходные данные:
true, если n простое, иначе false.

Ограничения:

• 0 ≤ n ≤ 10^9

• Решение должно работать быстрее, чем перебор всех делителей от 2 до n (достаточно O(√n)).

Пример:
Вход: n = 17
Выход: true

Вход: n = 100
Выход: false