Ganzzahlige ungefähr gleich große Teiler finden

...komplette Frage anzeigen

3 Antworten

Für ungerade Zahlen könntest du dir das angucken:
http://de.wikipedia.org/wiki/Faktorisierungsmethode_von_Fermat

In Delphi:

  n := 27;
  a := Math.Ceil(sqrt(n));
  i := -1;
  repeat
    i := i + 1;
    x := a + i;
    y := sqrt(math.Power(x, 2) - n);
  until (y = Math.Floor(y)) or (i>=C_MAX_INC);

  if i = C_MAX_INC then
    Memo1.Lines.add(Format('Naheliegensten Teiler von %0.0f: %0.0f, %0.0f', [n, 1.0, n]))
  else
    Memo1.Lines.add(Format('Naheliegensten Teiler von %0.0f: %0.0f, %0.0f', [n, x+y, x-y]));

Wurzel ziehen und < Ergebnis

So ganz ad hoc fällt mir folgender Algorithmus ein (es gibt sicher auch "intelligentere"):

Sei A der Flächeninhalt des Rechtecks.

Die Seitenlänge a eines Quadrates mit diesem Flächeninhalt hat, ist dann:

a = Wurzel ( A )

Sofern a ganzzahlig ist, hat man die Lösung schon gefunden ( a * a )

Sonst setzt man b = INT ( Wurzel ( A ) ), bildet also den gazzahligen Anteil von Wurzel ( A ), und prüft, ob A / b ganzzahlig ist.

Wenn ja, dann ist die Lösung gefunden ( b , A / b ) , sonst setzt man b = b - 1 und prüft, wieder, ob A / b ganzzahlig ist usw.

Spätestens bei b = 1 gibt es eine Lösung ( 1 , A )

.

IF Wurzel ( A ) = INT ( Wurzel ( A )

THEN PRINT ( a , a )

ELSE {

b = INT ( Wurzel ( A ) ) ;

WHILE b > 1 AND A / b <> INT ( A / b ) b = b - 1

PRINT ( b , A / b )

}

Setzt man hier A = 24 so wird zunächst geprüft:

Wurzel ( 24 ) = INT Wurzel ( 24 ) ?

Das ist nicht der Fall, also wird gesetzt:

b = INT ( Wurzel ( A ) ) = 4

Da 24 / 4 = 6 = INT ( 24 / 4 ) ist, bricht die WHILE-Schleife sofort ab, ohne durchlaufen zu werden und es wird

4 6

ausgegeben.

Was möchtest Du wissen?