primfaktorzerlegung

13.06.2013, 19:51

sarah45

primfaktorzerlegung

Meine Frage:
Hallo,
kann mir jemand erlären, wie man die Primfaktoren findet ?

Meine Ideen:
Defintion:
Wenn eine natürliche zahl a > 1 gleich dem produkt von k Primfaktoren ist, dann heißt dieses Produkt Primfaktorzerlegung von a. Ist a eine Primzahl, dann heißt a Primfaktorzerlegung von a

13.06.2013, 19:56

Theend9219

Auf diesen Beitrag antworten »

RE: primfaktorzerlegung
Hallo,
Man testet einfach, durch welche Primzahlen sich eine Zahl ohne Rest teilen läßt z.B

18 . Da fängt man mit der Teilbarkeit der ersten Primzahl 2 an
18 durch 2 = 9
dann testet man mit der 9 weiter
da geht die 2 nicht aber die 3
9 durch 3 = 3
und nun die 3 ... nicht durch 2 teilbar aber durch 3
und 3 durch 3 = 1
also folgt
18 = 2*3*3

Liebe Grüße

14.06.2013, 11:07

Mystic

Auf diesen Beitrag antworten »

RE: primfaktorzerlegung
@Theend9219

Deine Beschreibung lässt jetzt mehr Fragen offen, als sie beantwortet... geschockt

Ok, man testet also die Teilbarkeit durch 2 und 3... Wenn man aber dann noch nicht fertig ist, wie in deinem Beispiel, wie geht es danach weiter? Welche Zahlen werden als nächstes auf Teilbarkeit getestet und vor allem bis zu welcher Grenze? verwirrt

Eine mögliche Antwort auf alle diese Fragen stellt der Algorithmus dar, welcher dem nachfolgenden Maple-Programm zugrunde liegt, welches - so hoffe ich wenigstens - selbsterklärend sein sollte...

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

primefactors:=proc(nn::posint)
   local d:=2,n:=nn,s:=NULL,t:=5;   
   while n mod 2 =0 do n:=n/2; s:=s,2 end do;
   while n mod 3 =0 do n:=n/3; s:=s,3 end do;   
   do
      if t*t>n then 
         if n>1 then s:=s,n end if;
         return [s] 
      end if;
      while n mod t =0 do n:=n/t; s:=s,t end do;
      t:=t+d; d:=6-d
   end do
end:

primefactors(123456789);
                       [3, 3, 3607, 3803]

Neue Frage »

Antworten »

primfaktorzerlegung

Verwandte Themen