Легко Решено: 7 Процент решений: 38.9%

Prime Number Check

Decide whether a number is prime.

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

  • Test divisibility with the % operator
  • Stop checking at the square root of n
  • Handle 0, 1 and 2 as special cases

Условие

Показать перевод

A prime number is greater than 1 and divisible only by 1 and itself. Checking divisors up to the square root of n is enough.

Implement is_prime(n).

Input

n: The number to test.

Output

Return true if n is prime, otherwise 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 has no divisors other than 1 and 29.

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

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

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

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

Пояснение

21 = 3 × 7, so it is not prime.

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

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

Подсказка 1

Handle numbers below 2 first; they cannot be prime.

Подсказка 2

Test possible divisors only up to the square root of the number.

Подсказка 3

Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.

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

O(sqrt(n)) time, O(1) extra space

Ссылки

Это задание адаптировано для 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-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.