Entwickler-Ecke :: Thema anzeigen - Kombination von Primzahlen ermitteln

furtuna - So 11.11.07 20:59
Titel: Kombination von Primzahlen ermitteln

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!!

dummzeuch - So 11.11.07 21:04
Titel: Re: Kombination von Primzahlen ermitteln

furtuna hat folgendes geschrieben:

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

furtuna - So 11.11.07 21:17

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!!

Gausi - So 11.11.07 21:34

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 ;-)

Logikmensch - Mo 12.11.07 11:03

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?

Gausi - Mo 12.11.07 11:12

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 :mrgreen:

jasocul - Mo 12.11.07 11:40

:shock: 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.

Gausi - Mo 12.11.07 12:12

@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.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!