x*y=z Lösungsmenge

[Neutral General]

Hi,

Ich habe eine Zahl z (Integer, also Element Z) gegeben und will alle ganzen Zahlen x,y ausrechnen sodass gilt x*y = z.
Wie kann ich das mit Delphi ausrechnen ? :|

Gruß
Neutral General

[mkinzler]

Wohl nur manuell ( Annahme y > x sont x <-> y

Delphi-Quellcode:

for y := z downto x do
  if z mod y = 0 then  x:= z/y;
...

[Edit: to durch downto ersett]

[Der_Unwissende]

Hi,
überleg dir doch einfach mal wie man das machen könnte. Einfachster Weg, du setzt alle Ganzzahlen ein (kleiner Tipp vorab, es sind ein bisschen viele). Also kommst du sicher schnell auf die Idee, dass kein Faktor größer als Z sein darf und irgendwie ist Z und 1 immer eine Möglichkeit.
Die restlichen Zahlen sind also? Kannst mal überlegen welche Zahlen du maximal betrachten musst, sind natürlich bei weitem nicht alle zwischen 0 und z!

Ja, und wie man eine Schleife programmiert und einsetzt, das weißt du sicherlich.

Gruß Der Unwissende

[JasonDX]

Ich wuerde mit Primzahlzerlegung von z ansetzen - ginge IMO schneller, oder wenigstens mathematisch eleganter ;)

greetz
Mike

[dino]

und die Primkfaktozerlegung macht man, indem man alle integer der Menge [2;z/2] nimmt und überprüft, ob z mod diese Zahl = 0 ist

dann haste auch direckt die andere Zahl, die du ja dann nichtmehr überprüfen musst

oder noch besser:

bei ein einfangen und wenn z mod x = 0 ist x und z/x in deinem arry oder was auch immer speichern (array of booleans wäre da gut) und zusätzlich das z/x in iene variable speichern, weil sobald du mit x an die Zahl angelangt bist, brauchst du sie nicht mehr überprüfen und bist fertig

[Jürgen Thomas]

Zitat:

Zitat von dino

bei ein einfangen und wenn z mod x = 0 ist x und z/x in deinem arry oder was auch immer speichern (array of booleans wäre da gut) und zusätzlich das z/x in iene variable speichern, weil sobald du mit x an die Zahl angelangt bist, brauchst du sie nicht mehr überprüfen und bist fertig

Entschuldigung: Kannst Du das nochmal formulieren und mit Kommata versehen - Subjekt/Prädikat/Objekt, Nebensätze richtig beginnen und beenden, dazu Tippfehler korrigieren? Ich habe bei diesem Satz überhaupt nichts verstanden. Jürgen

[Khabarakh]

Zitat:

Zitat von dino

[2;z/2]

[2;Sqrt(z)]
In der Code-Lib gibt es eine optimierte Version dieses Probedivision-Verfahrens, daneben existieren natürlich auch noch effizientere Verfahren.

[edit]Whoops :stupid: [/edit]

[Ratte]

Zitat:

Zitat von Khabarakh

Zitat:

Zitat von dino

[2;z/2]

[2;Sqrt(2)]

[2;SQrt(z)] !!!!!
mfg,
ratte

[dino]

Zitat:

Zitat von Jürgen Thomas

Zitat:

Zitat von dino

bei ein einfangen und wenn z mod x = 0 ist x und z/x in deinem arry oder was auch immer speichern (array of booleans wäre da gut) und zusätzlich das z/x in iene variable speichern, weil sobald du mit x an die Zahl angelangt bist, brauchst du sie nicht mehr überprüfen und bist fertig

ups

also:

var i,i2:integer
var drin:array[1..z] of boolean

i:=1

repeat

if z mod i = 0 then begin drin[i]:= true; drin[z/i]:= true; i2:=z/i end;

inc(i)

until i>=i2

so klar?

[dino]

meins ist mehr ne skizze als ein Programm.

und perfeckt ist es auch nicht, soll nur meinen, dass man da auch selbst drauf kommen kann

[Cöster]

Zitat:

Zitat von dino

Zitat:

Zitat von Jürgen Thomas

Zitat:

Zitat von dino

bei ein einfangen und wenn z mod x = 0 ist x und z/x in deinem arry oder was auch immer speichern (array of booleans wäre da gut) und zusätzlich das z/x in iene variable speichern, weil sobald du mit x an die Zahl angelangt bist, brauchst du sie nicht mehr überprüfen und bist fertig

ups

also:

var i,i2:integer
var drin:array[1..z] of boolean

i:=1

repeat

if z mod i = 0 then begin drin[i]:= true; drin[z/i]:= true; i2:=z/i end;

inc(i)

until i>=i2

so klar?

Sicher, aber dir scheinen die Posts von Khabarakh und Ratte noch nicht klar zu sein: until i>=Sqrt(z) :wink:

Edit: Bei größeren Zahlen nehm ich aber an, dass es mit Primfaktorzerlegung schneller geht. Die dann aber natürlich nicht so machen, wie in Beitrag #5 beschrieben.

[dino]

wie macht mans denn? :)

[Jürgen Thomas]

Zitat:

Zitat von dino

ups

also: // usw.

so klar?

Bei meiner Nachfrage in #6 ging es mir weder um Mathematik noch um Programmierung, sondern um die deutsche Sprache: Vor etwa 30 Jahren hatte ich Mathematik studiert und ähnliche Probleme bearbeitet. Aber bei Deiner von mir kritisierten Aussage habe ich überhaupt nichts - nichts! - verstanden.

So etwas passiert in Foren leider häufiger; aber das war mir zuviel. Ich bitte darum:

1. zuerst denken
2. dann formulieren
3. dann kontrollieren, auch Lesbarkeit und Verständlichkeit für den Leser
4. dann absenden

und nicht mehrere dieser Schritte vergessen. Jürgen

[dino]

ja tschuldige, aber darum hab ichs ja dann ohne Deutsch formuliert...

[Cöster]

Zitat:

Zitat von dino

wie macht mans denn? :)

Ich würd's so machen:

Code:

Laufvariable I, Anfangswert: 2
Wiederhole:
   Wenn die Zahl Z nicht durch I teilbar ist
      -> I erhöhen
   sonst
      -> I zu den Primfaktoren hinzufügen
      -> Z := Z div I
bis I*I > Z

Das könnte man dann noch dadurch optimieren, dass man z.B. I nicht um 1 erhöht, sondern, nachdem man mit der 2 fertig ist, immer um 2 erhöht (also nur ungerade Zahlen probiert). Man könnte sogar alle Primzahlen bis zu einer bestimmten Grenze in einem array liegen haben und mit I dann die einzelnen Array-Werte durchgehen.

Die Möglichkeiten für x bzw. y sind die unterschiedlichen Produkte aller möglichen Kombinationen der Primfaktoren.

[Khabarakh]

Ich habe doch schon längst erwähnt, dass es in der Codelib eine optimierte Trial Division-Variante gibt :roll: . Und wo man noch bessere Verfahren finden kann, dürfte hoffentlich bekannt sein.

[alzaimar]

Nehmt doch bitte mkinzlers Vorschlag:

Delphi-Quellcode:

For x := 2 to Trunc (sqrt(z)) do
  if z mod x = 0 then 
    OUTPUT (x,z div x)

Wobei man sich bei OUTPUT ja denken kann, das hier z.B. in einem Memo irgendwas ausgegeben wird.
Mit Primfaktoren geht das auch, ist vielleicht schneller, aber dezent komplizierter. Das Problem ist ja, das man fast alle Variationen der Primfaktoren erzeugen muss. Möglich, aber nicht trivial.

Wenn es nicht um astronomisch hohe Zahlen geht, dann reicht doch die o.g. Variante.

Vermutlich geht es auch mit diophantischen Gleichungen und/oder Ansätzen aus der Kongruenzmathematik, aber da bin ich überfragt.