Algoritmus für 2 ähniche Produkte von Primfaktoren

Erste Frage Aufrufe: 757     Aktiv: 28.03.2019 um 19:21
3

 

Hallo,

ich wollte wissen, gibt es einen Algorithmus der aus den Primfaktoren einer natürlichen Zahl zwei Produkte ohne gemeinsamen Primfaktor bildet sodass die Differenz zwischen den beiden minimal ist.

Im Prinzip suche ich also eine gute Methode für die Darstellung einer natürlichen Zahl durch das Produkt zweier natürlicher Zahlen mir möglichst geringer Differenz.

Ich wollte mich in nächster Zeit mal damit beschäftigen und da wäre es blöd wenn es das schon gibt.

Viele Grüße,

Ingwe

 

 

Diese Frage melden
gefragt

Schüler, Punkte: 35

 

Sehr interessante Frage, ich kenne keinen... Kann mir aber gut vorstellen, dass irgendwer sich schon damit beschäftigt hat ':D


Ich werde jetzt bestimmt Mal druber nachdenken! :)

   ─   jojoliese 28.03.2019 um 22:24
Kommentar schreiben
1 Antwort
0

Ich als Informatikstudent weiß da leider auch keine so genaue Antwort, aber ich kann es mir so vorstellen:

Nehmen wir mal die 100  Beispiel:

Die Primfaktorzerlegung ist somit 5*5*2*2.

Somit ergibt sich folgendes int Array:

[5, 5, 2, 2].

Wir durchlaufen dieses Array und fangen beim Index 0 an.

int zahl1 = 1

int zahl2 = 1

int zahl1faktoren[] //eigentlich eine Liste

int zahl2faktoren[]

int Faktor

for (int i=0; i < array.size(); i++)

       if zahl1faktoren == NULL 

           zahl1faktoren.add(array[i])

           zahl1 = zahl1 * array[i]

           continue

       if zahl1faktoren.size() > zahl2faktoren.size() && not zahl2faktoren.contains(array[i]) && not zahl1faktoren.contains(array[i])

            zahl2aktoren.add(array[i])

            zahl2 = zahl2 * array[i]

            continue //zurück zum Anfang der for Schleife

       if zahl1faktoren.contains(array[i])

            zahl1 = zahl1 * array[i]

     if zahl2faktoren.contains(array[i])

            zahl2 = zahl2 * array[i]

 

 

Ich hoffe mein Pseudocode ist nicht zu unordentlich :D es würde bei zahl1 25 und bei zahl2 4 raus kommen. Ist es das was du meinst?

Diese Antwort melden
geantwortet

Punkte: 50

 

Oh ja habe noch den Fall vergessen, dass es einen Faktor gibt, der nicht in Liste1 ist, aber rein soll und wann es passieren soll. Da würde ich sagen, dass es unter der Bedingung geschehen soll, dass der Faktor nicht in Liste1 ist und Liste1 die gleiche Länge wie Liste 2 hat. 


 


Außerdem müsste man glaube ich das Array erstmal absteigend sortieren, aber ich kann mich auch irren.

   ─   dd28924 28.03.2019 um 23:53

Kommentar schreiben