Sie sind nicht angemeldet. Bitte melden Sie sich an oder registrieren Sie sich.
Seiten 1
Sie anmelden oder registrieren um eine Antwort zu verfassen
Also: Wie kann man die Primfaktorzerlegung für x machen, ohne alle Primzahlen zu berechnen? Wie weiß ich, aber den Beweis kenn ich nicht. Sprache egal, da ich ja weiß wie.<P>Wer kanns lösen (@odoggy: also such dir mal die plattformunabhängigste Sprache raus und zwar eineindeutig [img]images/icons/wink.gif" border="0[/img])? Für den dazugehörigen Beweis wär ich doppelt dankbar.
Da brauchst Du doch blos bei mathos Sache reinsehen - mit dem modulo Operator (%). Fertig ist der Lack. Oder was stellst Du Dir vor?
Hey wintel, das weiß ich. Jedoch: Ich will nicht erst alle Primzahlen <= n ermitteln und die dann testen. Wie macht mans? Ich weiß es. Es soll die Primfaktorzerlegung bleiben. Der modulo is hier wirklich praktisch. Also, wer zB in JS eine Lösung kennt, posten. Wers beweisen kann, auch.
Ich weiß ja nicht was Du unter Primfaktorzerlegung verstehst. Ich dachte Du willst nen Test auf Primzahl --> ja/nein. So in der Art: ist x=17654 eine Primzahl.<BR>Wennde das meinst, dann einfach ne Schleife i=(2,sqrt(x)+1,1) und testen mit %. Falls == 0, dann keine.<BR>Ansonsten schreib mal ein Bsp. für Primfaktorzerlegung - ist schon ne Weile her, dass ich mal sowas wissen musste [img]images/icons/smile.gif" border="0[/img]<p>[ 04.06.2001: Beitrag editiert von: wintel ]
Hehe, endlich weiß ich mal mehr als jemand anders [img]images/icons/wink.gif" border="0[/img]<P>Die Primfaktorzerlegung ist die einzige Möglichkeit, eine Zahl als Produkt von Primzahlen zu schreiben. So berechnet man in der Schule auch gerne den ggT oder den kgV.<BR>Bsp.:<BR>18 = 2 * 9<BR> <B>= 2 * 3 * 3</B><P>12 = 2 * 2 * 3<P>16 = 2 * 8<P>85 = 5 * 17<P>100 = 2 * 2 * 5 * 5<P>17 = 17<P>Also, das sind glaub ich genugn Beispiele.
Aso, das kgV - das sagt mir was.<BR>Kleine Ungenauigkeit: 16=2*2*2*2<P>Das Ablegen der Primzahlen geht zwar schnell:<BR>import java.lang.*;<BR>class prime {<BR>static final int max = 100; <BR>static final int startat = max - 100;<BR>static int n = max;<BR>static double limit; <P>public static void main (String[] args) {<BR>boolean numberpool[] = new boolean [n];<BR>for (int i=2; i<n; i++){<BR>numberpool[i]=true;<BR>}<BR>limit = Math.sqrt(n);<BR>int j=2; <BR>for (int i=j+j; i<n; i=i+j){<BR>numberpool[i]=false;<BR>}<BR>for (j=3; j<=limit; j=j+2){<BR>if (numberpool[j]==true){<BR>for (int i=j+j; i<n; i=i+j){ numberpool[i]=false;<BR>}<BR>}<BR>}<BR>System.out.println("Primzahlen von " + startat + " bis " + max + ":");<BR>for (int i=startat; i<max; i++){<BR>if (numberpool[i]==true){<BR>System.out.print(i + " ");<BR>}<BR>}<BR>}<BR>}<BR>aber wen Du das nicht willst, dann schau Dir mal folgendes an:<BR>int max,i;<BR>max=java.lang.Math.sqrt(x)+1;<BR>int numberpool[] = new int [max];<BR>i=2;<BR>ii=0;<BR>while (i<max) {<BR>if (x%i == 0) {<BR>x=x/i; // zwar etwas forsch (Rechnerungenauigkeit) geht aber --> ich wuerde zur Sicherheit eigentlich noch was draufhaun<BR>numberpool[ii]=i;<BR>ii++;<BR>i=2;<BR>}<BR>else {i++;}<BR>if (x<=1) {break;}<BR>}<P>So denke ich müßte es doch gehen?!<p>[ 04.06.2001: Beitrag editiert von: wintel ]
Ungefähr. Also in VC++ is es ganz einfach. Wozu sqrt, die Teiler können doch auch größer sein (n/2) oder die Zahl ne Primzahl selbst! Gut soweit. Also, mal den Beeeweis nur noch. Die Primzahlen hersfinden ist wirklich langwierig.
Hab genug geplauscht für Heute - muß ja auch noch irgendwann Arbeiten. Morgen is auch noch ein Tag.<BR>Übrigens: Die Wurzel reicht als Index meiner Meinung nach voll zu - denk noch mal drueber nach.
In C:<P>#define maxZER(val) val <P>int val,i,ii=0,mult[MAX];<BR>if (val > 2)<BR>{<BR>for (i=2;i<=maxZER(val);i++) {<BR> while(val % i == 0) {<BR> mult[ii]=i;<BR> val /= i;<BR> }<BR>}<BR>}else{<BR>mult[0]=1;<BR>}<P>Als Abbruchbedingung ginge, ob die Mult. der Elemente val gibt. Warum maxZER(val)=val? Sollte val eine Primzahl sein oder z.B. 18:: sqrt(18)=4,242640687... 18=2*<B>9</B>. Also, bis dänn.
@whiteheart:<BR>nur so als Anmerkung:<BR>Ich bin kein Freund von kurzschreibweisen val /= i;. Es verschlechtert die Lesbarkeit enorm. Sicher siehts technisch aus, aber die 3 Buchstaben mehr machen das Kraut nicht fett...<P>Ich hab nich verstanden was Du meinst. Aber erstmal noch eine Verbesserung/Berichtigung.<BR>In dem oberen Code muß in die while-Schleife folgendermaßen aussehen:<BR>while (i<max) {<BR>if (x%i == 0) {<BR>x=x/i;<BR>numberpool[ii]=i;<BR>// NEU Anfang<BR>numberpool[ii+1]=x;<BR>// NEU Ende<BR>ii++;<BR>i=2;<BR>}<BR>else {i++;}<BR>if (x<=1) {break;}<BR>}<P>Damit ist es vollkommen sauber.<BR>Bsp.:<BR>x=34 (2*17)<BR>max=sqrt(34)+1=6 (max ist integer und damit wird nur der ganzzahlige Teil genommen - ohne Rundung)<BR>bei i=2 --> numberpool[1]=i=2<BR>x=34/2=17 --> numberpool[1+1]=x=17<BR>Anm.: hier kommt das mit der Rechnerungenauigkeit; ich kann ein Lied von real-Zahlen (oder float) singen und was dabei für Sauereien passieren; deshalb hätte ich eigentlich geschrieben (jetzt nicht in Java, sondern allgemein) x=(x/i+0.0001) - oder gerundet<BR>weitere Duchläufe keinen Erfolg, fertig.
Nach meinen Überlegungen ist das aber alles überflüssig... dazu später mehr
apropos runden: bei integer-Arith. is das nich notw.<P>entschuld für 2*9, 2*17 solltes sein, war spät...<P>bis dänn, wills noch erläutern, wieso das mit dem sqt vergebl. Liebesmühe is...
@whiteheart:<BR>"apropos runden: bei integer-Arith. is das nich notw."<BR>Aber aber mein lieber Freund! Man sollte sich schon bewußt sein, was man macht!!!<BR>Gesetzt den Fall, der Rechner ist mal schlecht drauf (ist ja auch nur ein Mensch [img]images/icons/wink.gif" border="0[/img]), kann nach einigen Rechnungen z.B. für 2/2=0.999999999999999 rauskommen.<BR>Dann wäre die Zuweisung einfach so auf einen Integer=0!!!!!!!!<BR>Meiner Meinung nach sollte jeder, der wirklich rechnet auch wissen, was z.B. für interger/float, oder integer+float rauskommt. Und dann die entsprechenden Vorsichtsmaßnahmen ergreifen.<P>"2*17 solltes sein" --> dafür hab ich Dir doch das Bsp. gemacht.<P>Ich versteh immer nur Bahnhof bei Dir. Kannst Du Dich nicht mal klar und deutlich ausdrücken?
Fakt ist, dass für Integer und Gleitkomma-Arith. unterschiedliche Proz.-Units verwadt werden.
tatsächlich berechnet meine Meth. zum letzten Teiler und stoppt dann<P>12<BR>i=2<BR>6<BR>i=2 ; 2<BR>3<BR>i=3<BR>1<BR>1<3 !! Stopp<P>Primzahlen zu berechnen lohnt sich nur, sollten mehrere Zahlen berechnet werden
Was will uns der Dichter wohl damit sagen??? - Weiß nicht was Du willst!<P>Schau mal zu matho's Thema. Hab bald keine Lust mehr zu Arbeiten und will verduften. Schaffen wir aber vorher noch das Problem zu lösen.
val = 12<BR>1. Durchlauf:<BR>i = 2<BR>put 2<BR>val = 6<BR>--'while' weiter<BR>i = 2<BR>put 2<BR>val = 3<BR>2. Durchlauf<BR>i = 3<BR>put 3<BR>val = 1<BR>--ABBRUCH, da 3 <= 1 nicht wahr<P>das wären die Zustände in meiner Version für 12<P>Capiche [img]images/icons/wink.gif" border="0[/img]?
@/=-Kritik: Ich finds hier natürlicher: würdest du sagen "Wenn man x durch i dividiert erhält man das neue x?" Nicht eher "Teile x durch i"?
@whiteheart:<BR>Für das Bsp. mit 12: genau das macht doch auch mein code-Stück. Haben wir also beide die Lösung. Hättest Du doch garnicht fragen brauchen [img]images/icons/wink.gif" border="0[/img]<P>Was ist nun mit der Wurzel zum Bestimmen der oberen Grenze für die while-Schleife?<P>Noch mal was prinzipielles:<BR>Ich halt an der Uni Seminare (also Unterricht). Nebenher auch noch Mathe und Physik Nachhilfe für Schüler und Studenten. Will damit sagen, daß ich eigentlich schon weiß, was ich jetzt sagen werde. Ich finde es gut, wenn man Sachen auf das wesentliche reduzieren kann und sich so ausdrücken kann, das es auch jemand ohne große Ahnung versteht. Das zeichnet für mich jemanden aus, der eine Sache verstanden hat: sie so erklären zu können, daß sie auch die Oma von nebenan versteht.<BR>Solltest mal darüber nachdenken.<P>Gruß wintel
bei 12 ist die Wurzel doch 3,... +1 also abgerundet 4, bis 4 gehts also, das etw. größer ist. also geht das mit der Wurzel weiter. natürlich, bei zB 34 ist es etw. schneller, da es nur 2,3,4,5,6 und 17 prüft. wenn man allerdings vorher bereits alle Primzahlen berechnet hat, ist dafür auch eher meine Methode (mit Abwandlungen nat.) geeignet.
Interessant fände ich tatsächlich aber den Beweis warum meine (ist etwas einfacher) die Primfaktorzerlegung berechnet und nicht irgendwelche Teiler ausgibt. Natürlich kenne ich den Grund warum, möcht aber mal sehn, wie kurz dafür n Beweis ist. Ohne Beweis daerf man die Methode ja nich anwenden.
ach ja, die Primzahlen <= 34: <B>2,3,5,7,11,13,17</B>,19,23,29,31,ENDE berechnet werden also nur die fetten
Womit gezeigt wäre, dass Fakten herauszufinden viel einfacher ist, als sie zu beweisen.
Hmm, der Beweis scheint wirklich schwierig zu sein. Wär aber wirklich praktisch (nur so kann man daraus mehr folgern, um weitere Probleme zu lösen).
Seiten 1
Sie anmelden oder registrieren um eine Antwort zu verfassen
Powered by PunBB, unterstützt von Informer Technologies, Inc.
Currently installed 7 official extensions. Copyright © 2003–2009 PunBB.