Prime Number Check

Problem

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).

n: The number to test.

Return true if n is prime, otherwise false.

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

Beispiel 1

Eingabe:
n = 29

Erwartete Ausgabe:
expected = True

Eingabe:
long long n = 29;

Erwartete Ausgabe:
bool expected = true;

Eingabe:
long n = 29;

Erwartete Ausgabe:
bool expected = true;

29 has no divisors other than 1 and 29.

Beispiel 2

Eingabe:
n = 21

Erwartete Ausgabe:
expected = False

Eingabe:
long long n = 21;

Erwartete Ausgabe:
bool expected = false;

Eingabe:
long n = 21;

Erwartete Ausgabe:
bool expected = false;

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

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Handle numbers below 2 first; they cannot be prime.

Hinweis 2

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

Hinweis 3

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

Erwartete Komplexität

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

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.