Python Prime Checker-Algorithmus

Überprüfen Sie mit Python, ob eine Zahl eine Primzahl ist. Führen Sie unseren interaktiven Algorithmus aus, um eine effiziente mathematische Iteration und Wurzelauswertung zu sehen.

Versuchen Sie es im Editor

Übersicht

Eine Primzahl ist eine positive ganze Zahl größer als 1, die außer 1 und sich selbst keine positiven Teiler hat.

Der ineffizienteste Weg, nach einer Primzahl zu suchen, ist die Iteration bis zur Zahl selbst. Eine wirkungsvolle Optimierung besteht darin, die Teilbarkeit nur bis zur Quadratwurzel der Zahl zu prüfen.

Code- und Ausführungsausgabe

Effizienter Primzahlprüfalgorithmus, der die O(sqrt(n))-Optimierung demonstriert.

prime_checker.py

Versuchen Sie es im Editor

import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
        
    max_divisor = math.isqrt(n)
    for i in range(3, max_divisor + 1, 2):
        if n % i == 0:
            return False
            
    return True

test_numbers = [2, 10, 17, 25, 97]
for num in test_numbers:
    status = "Prime" if is_prime(num) else "Not Prime"
    print(f"{num:2d} -> {status}")

Terminal-Ausgabe

 2 -> Prime
10 -> Not Prime
17 -> Prime
25 -> Not Prime
97 -> Prime

Schrittweise Umsetzung

Kryptographie und Hashing-Algorithmen
Pädagogische Mathematik und Siebtheorie
Backend-Validierung für sichere Schlüssel

Häufig gestellte Fragen

Warum nur bis zur Quadratwurzel prüfen?

Wenn $n = a \times b$, dann muss mindestens einer der Faktoren ($a$ oder $b$) kleiner oder gleich der Quadratwurzel von $n$ sein. Daher ist eine höhere Überprüfung überflüssig.