Algoritmus für 2 ähniche Produkte von Primfaktoren


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

 

 

gefragt vor 1 Monat, 3 Wochen
i
ingwe,
Schüler, 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, kommentiert vor 1 Monat, 3 Wochen
Kommentar schreiben Diese Frage melden
1 Antwort
1

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?

geantwortet vor 1 Monat, 3 Wochen
d
 

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, kommentiert vor 1 Monat, 3 Wochen
Kommentar schreiben Diese Antwort melden

Deine Antwort
Hinweis: So gibst du Formeln ein.