Primzahl-Prüfung

Problem

Eine Primzahl ist größer als 1 und nur durch 1 und sich selbst teilbar. Es genügt, die Teiler bis zur Quadratwurzel von n zu überprüfen.

Implementiere is_prime(n).

n: Die zu prüfende Zahl.

Gib true zurück, wenn n eine Primzahl ist, andernfalls 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 hat keine anderen Teiler als 1 und 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, daher ist sie keine Primzahl.

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

Hinweis 1

Behandle Zahlen unter 2 zuerst; sie können nicht prim sein.

Hinweis 2

Teste mögliche Teiler nur bis zur Quadratwurzel der Zahl.

Hinweis 3

Achte auf gerade Zahlen und doppelte Faktoren, denn ein Teiler reicht, um Primzahl zu widerlegen.

Erwartete Komplexität

Zeit O(sqrt(n)), zusätzlicher Speicher O(1)

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