Все задачи
Легко Решено: 7 Процент решений: 38.9%

Проверка на простое число

Определите, является ли число простым.

Чему вы научитесь

  • Проверять делимость оператором %
  • Останавливаться на квадратном корне из n
  • Учитывать 0, 1 и 2 как особые случаи

Условие

Простое число — это число больше 1, которое делится только на 1 и само себя. Достаточно проверять делители до квадратного корня из n.

Реализуйте функцию is_prime(n).

Ввод

n: Число для проверки.

Вывод

Верните true, если n — простое, иначе false.

Ограничения

-1,000 ≤ n ≤ 1,000,000,000,000

Примеры

Пример 1
Ввод:
n = 29

Ожидаемый вывод:
expected = True
Ввод:
long long n = 29;

Ожидаемый вывод:
bool expected = true;
Ввод:
long n = 29;

Ожидаемый вывод:
bool expected = true;

Пояснение

У числа 29 нет делителей, кроме 1 и 29.

Пример 2
Ввод:
n = 21

Ожидаемый вывод:
expected = False
Ввод:
long long n = 21;

Ожидаемый вывод:
bool expected = false;
Ввод:
long n = 21;

Ожидаемый вывод:
bool expected = false;

Пояснение

21 = 3 × 7, поэтому оно не является простым.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Сначала обработайте числа меньше 2; они не могут быть простыми.

Подсказка 2

Проверяйте возможные делители только до квадратного корня числа.

Подсказка 3

Следите за чётными числами и повторяющимися множителями: одного делителя достаточно, чтобы число было не простым.

Ожидаемая сложность

время O(sqrt(n)), доп. память O(1)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 ННикита Python 1,059 ms - 5/5 Посмотреть код
2 AAmir Python 1,098 ms - - Посмотреть код
3 KKKaneki Ken Python 1,137 ms - 5/5 Посмотреть код
4 JPJittipat Phonhan Go 1,547 ms - 5/5 Посмотреть код
5 GTGarlic The Destroyer Rust 1,759 ms - 2/5 Посмотреть код
6 HJhettory Jurash C++ 4,287 ms - 4/5 Посмотреть код
7 PTphúc thịnh phạm C++ 4,447 ms - 4/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 7 полных решений Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.