Zum Inhalt springen
Inhaltsverzeichnis öffnen
Kapitel 3Aufbau23 Min.

Warum die Quadratwurzel genügt

Teilerpaare und die Anzahl der Teiler · Abschnitt 10 von 64

Satz

Suchgrenze

In jedem Faktorprodukt n=dqn=dq liegt mindestens einer der beiden Faktoren höchstens bei n\sqrt n.

Checkliste

Vollständige Teilersuche

  • Kandidaten von 1 bis ⌊n⌋\lfloor\sqrt n\rfloor testen.

  • Zu jedem Treffer den Partner n/dn/d ergänzen.

  • Liste sortieren.

  • Bei einer Quadratzahl die Quadratwurzel nur einmal aufnehmen.

Typischer Fehler

Nicht blind bis $n$ testen

Alle Zahlen bis nn zu testen ist korrekt, aber unnötig. Bis n\sqrt n genügt – und du hast zugleich einen Vollständigkeitsbeweis.