hallo leute, ich bin ein anfänger und komme bei einer aufgabe einfach nicht mehr weiter:

Der User soll eine Zahl eingeben z.B 36 und das Programm liefert eine Kombination von Primzahlen, deren Produkt der eingegebenen Zahl entspricht.

So eine Grobe idee hab ich schon aber ich würd mich freuen, wenn mir jemand den Code dieses Programms zeigen könnte, weil das mir momentan am meisten helfen wird.
Danke im Vorraus!!

furtuna hat folgendes geschrieben:

hallo leute, ich bin ein anfänger und komme bei einer aufgabe einfach nicht mehr weiter: Der User soll eine Zahl eingeben z.B 36 und das Programm liefert eine Kombination von Primzahlen, deren Produkt der eingegebenen Zahl entspricht. So eine Grobe idee hab ich schon aber ich würd mich freuen, wenn mir jemand den Code dieses Programms zeigen könnte, weil das mir momentan am meisten helfen wird. Danke im Vorraus!!

Grundregel hier: Hausaufgaben sollen selbst gemacht werden.

Die Loesung ist doch recht einfach:

1. Primzahlen ermitteln bis sqrt(zahl)
2. feststellen, ob die Zahl jeweils dadurch teilbar ist
3. Naja, 2. muss natuerlich auch ermitteln, ob die zahl mehrfach durch die jeweilige Primzahl teilbar ist.

Das liesse sich dann noch optimieren, aber warum sollte man?

twm

Hallo und in der Entwickler-Ecke!

Wie sehen denn deine Ansätze aus? Dann kann man darauf ja aufbauen .

also vielleicht ist mein problem nicht richtig rübergekommen: ich kann schon ein programm schreiben, dass die primzahlen ermittelt, ja ja nicht zu glauben
Aber die Aufgabe will, das das Programm Die Kleinste Kombination von Primzahlen ausgibt.
Ich könnt ja eine Schleife schreiben, das alle möglichkeiten ausprobiert, aber sobald mehr als zwei primzahlen benötigt werden, wird die laufzeit kein ende nehmen. Daher suche ich eigentlich einen guten Algorithmus der das problem eleganter löst. Ich hoffe ich erwarte nicht zuviel, ich würd mich aber freuen,wenn mir jemand hilfestellung geben könnte. Danke!!

Das Problem verstehe ich jetzt nicht. Die Primfaktorzerlegung (und die suchst du ja scheinbar) ist eindeutig. Wenn du eine Liste von Primzahlen p1...pn gefunden hast, für die das Produkt die gesuchte Zahl ist, dann hast du auch die kleinste Zerlegung gefunden.

Ich kann dir das jetzt auf Anhieb nicht beweisen (war iirc auch etwas komplizierter), aber das ist so

Stimmt, Gausi. Ich sehe es genauso.

Vielleicht sollten wir Fortunas Beispiel der 36 nochmal aufgreifen. Also, von Hand mache ich folgendes:

x <= 36
p <= 2 (kleinste Primzahl)

Schleife:
ist x durch p teilbar?
nein --> Erhöhe p, bis auf nächste Primzahl (also von 2 auf 3, von 3 auf 5 etc.)
ja --> Gebe p aus, teile x durch p und nimm neues x, um zu 'Schleife' zu springen

Das ganze wiederhole, bis x=1 geworden ist.

Also kriegst Du:

2 (x wird 18 )
2 (x wird 9)
3 (x wird 3)
3 (x wird 1)
Fääättiisch, also 2*2*3*3 = 36

Wo genau ist da eine Endlosschleife?

Richtig, so kann man das machen. Die Frage, die man sich aber zunächst mal stellen kann ist: Gibt es neben der so gefundenen Zerlegung auch eine andere, die evtl. mit weniger Faktoren auskommt? Z.B. nicht 2*2*3*3, sondern 5*7 (was ja fast hinkommt).

Wenn es sowas gäbe, hätte man in der Tat ein Problem. Aber zum Glück gibt es das ja nicht

Gausi!
Verwirr die Leute doch nicht. Um es nochmal ganz deutlich zu sagen: Eine Primfaktorzerlegung ist eindeutig. Aber das wollte Gausi mit seinem letzten Satz auch sagen.

scheint mir eher ein Problem der verkorksten Aufgabenstellung zu sein.
Poste die doch mal, vielleicht hilft das weiter.

@jasocul: Das habe ich ja auch schon weiter oben gesagt . Es scheint hier aber wirklich das Problem die Aufgabenstellung zu sein, denn sowas

furtuna hat folgendes geschrieben:

Aber die Aufgabe will, das das Programm Die Kleinste Kombination von Primzahlen ausgibt.

macht ja nun nicht wirklich unbedingt Sinn.

Das hatte ich überlesen.