Beliebige ganze Zahl in zwei Faktoren zerlegen

Question

der Empfänger einer Nachricht bekommt zwei Zahlen und multiplizert diese miteinander. Mit dem Ergebnis macht er irgendwas weiter.

Meine Aufgabe als Sender der Nachricht ist es nun, vorher die große Zahl in zwei kleinere Zahlen zu zerlegen, damit die gewünschte große Zahl so gut wie möglich durch die zwei Faktoren abgebildet wird.

Wie würdet ihr da rangehen, ohne alle Varianten durchzuprobieren?

Knulli

Answer 1

Wie wäre es damit ?

wurzel aus der großen Zahl nehmen.

wenn das eine ganze Zahl ist, zweimal der gleiche Faktor

ansonsten von der Wurzel abwärts gehen, bis du auf einen

Teiler der großen Zahl triffst (endet spätestens bei 1)

und dann diesen Teiler und seinen komplementären nehmen.