matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheoriekgV,Algorithmus
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Zahlentheorie" - kgV,Algorithmus
kgV,Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

kgV,Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:43 Sa 24.10.2015
Autor: sissile

Aufgabe
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?


Hallo,
Ich bin auf der Suche nach einen Algorithmus für das Problem. (Die Implementierung am PC ist kein Problem und ist nicht Gegenstand meiner Frage)
Dazu habe ich gefunden:
1) Suche alle primzahlen von 1-20
2) Suche für jede dieser Primzahlen [mm] p_i [/mm] , das größte [mm] m_i [/mm] sodass [mm] p^{m_i} \le [/mm] 20
3) Multipliziere alle [mm] p^{m_i} [/mm] zusammen

Nun meine Frage, wieso funktioniert der Algorithmus?
Von der Zahlentheorie kenne ich nur:
Sind [mm] a_1,..,a_n \in \mathbb{N} [/mm] mit Primfaktorzerlegung [mm] a_i [/mm] = [mm] \prod_p p^{\alpha_i_p} (1\le [/mm] i [mm] \le [/mm] k), so besitzt [mm] kgV(a_1,..,a_n) [/mm] die Primfaktorzerlegung [mm] kgV(a_1,..,a_n)=\prod_p p^{max\{\alpha_1_p,..,\alpha_k_p\}} [/mm]
D.h. für den Algorithmus:
1) Suche alle primzahlen von 1-20
2) Suche die Primfaktorzerlegungen der Zahlen 1-20
3) Suche für jede Primzahl [mm] p_i [/mm] in den Primfaktorzerlegungen der Zahlen 1-20 die größte Anzahl der Vorkommen der Primzahl und bezeichne sie als [mm] m_i. [/mm]
4)  Multipliziere alle [mm] p_i^{m_i} [/mm] zusammen
Warum läuft sich das auf das selbe heraus?


Ich hoffe die Frage ist nicht zu trivial ;/
LG,
sissi


        
Bezug
kgV,Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 19:01 Sa 24.10.2015
Autor: Al-Chwarizmi


> What is the smallest positive number that is evenly
> divisible by all of the numbers from 1 to 20?
>  
> Hallo,
>  Ich bin auf der Suche nach einem Algorithmus für das Problem.
>  Dazu habe ich gefunden:
>  1) Suche alle primzahlen von 1-20
>  2) Suche für jede dieser Primzahlen [mm]p_i[/mm] , das größte
> [mm]m_i[/mm] sodass [mm]p^{m_i} \le[/mm] 20
>  3) Multipliziere alle [mm]p^{m_i}[/mm] zusammen
>  
> Nun meine Frage, wieso funktioniert der Algorithmus?
>  Von der Zahlentheorie kenne ich nur:
>  Sind [mm]a_1,..,a_n \in \mathbb{N}[/mm] mit Primfaktorzerlegung [mm]a_i[/mm]
> = [mm]\prod_p p^{\alpha_i_p} (1\le[/mm] i [mm]\le[/mm] k), so besitzt
> [mm]kgV(a_1,..,a_n)[/mm] die Primfaktorzerlegung
> [mm]kgV(a_1,..,a_n)=\prod_p p^{max\{\alpha_1_p,..,\alpha_k_p\}}[/mm]
>  
> D.h. für den Algorithmus:
>  1) Suche alle primzahlen von 1-20
>  2) Suche die Primfaktorzerlegungen der Zahlen 1-20
>  3) Suche für jede Primzahl [mm]p_i[/mm] in den
> Primfaktorzerlegungen der Zahlen 1-20 die größte Anzahl
> der Vorkommen der Primzahl und bezeichne sie als [mm]m_i.[/mm]
>  4)  Multipliziere alle [mm]p_i^{m_i}[/mm] zusammen
>  Warum läuft sich das auf das selbe heraus?
>  
>
> Ich hoffe die Frage ist nicht zu trivial ;/
>  LG,
>  sissi


Hallo sissi

der erste Algorithmus hat offenbar den Vorteil, dass man nicht für
jede einzelne der Zahlen die gesamte Primzerlegung ermitteln
muss.
Dass man sich das ersparen kann, wird durch folgende Überlegung
klar:  Sei p eine der Primzahlen und n(p) diejenige Zahl der
Grundmenge (hier nur die Menge der Zahlen von 1 bis 20), in
welcher der Faktor p in der höchsten Potenz, zum Beispiel [mm] p^k [/mm] auftritt.
Dann ist offensichtlich diese Potenz [mm] p^k [/mm] höchstens so groß wie
n(p) und damit auch höchstens gleich 20 .
Man findet also diese höchste Potenz [mm] p^k [/mm] schon heraus,
indem man einfach die höchsten Primzahlpotenzen in der Grundmenge
ermittelt.

LG ,   Al-Chw.    


Bezug
                
Bezug
kgV,Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:12 Sa 24.10.2015
Autor: sissile

Hallo;)
Danke für die Antwort.

> Hallo sissi
>  
> der erste Algorithmus hat offenbar den Vorteil, dass man
> nicht für
>  jede einzelne der Zahlen die gesamte Primzerlegung
> ermitteln
>  muss.
>  Dass man sich das ersparen kann, wird durch folgende
> Überlegung
>  klar:  Sei p eine der Primzahlen und n(p) diejenige Zahl
> der
>  Grundmenge (hier nur die Menge der Zahlen von 1 bis 20),
> in
>  welcher der Faktor p in der höchsten Potenz, zum Beispiel
> [mm]p^k[/mm] auftritt.
>  Dann ist offensichtlich diese Potenz [mm]p^k[/mm] höchstens so
> groß wie
>  n(p) und damit auch höchstens gleich 20 .

Ist alles klar.

>  Man findet also diese höchste Potenz [mm]p^k[/mm] schon heraus,
>  indem man einfach die höchsten Primzahlpotenzen in der
> Grundmenge
>  ermittelt.

Woraus kommst du zu der Folgerung?
Die [mm] p^k [/mm] (die k also gewählt wie im 2.ten Algorithmus nach der Zahlentheorie) sind höchstens gleich 20 hast du oben beschrieben.
Aber warum sind diese k genau die MAXIMALEN m sodass [mm] p^m \le [/mm] 20 wie in Algorithmus 1) beschrieben?

LG,
sissi

Bezug
                        
Bezug
kgV,Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 21:04 Sa 24.10.2015
Autor: felixf

Moin!

>  >  Man findet also diese höchste Potenz [mm]p^k[/mm] schon
> > heraus,
>  >  indem man einfach die höchsten Primzahlpotenzen in der
> > Grundmenge
>  >  ermittelt.
>
>  Woraus kommst du zu der Folgerung?
>  Die [mm]p^k[/mm] (die k also gewählt wie im 2.ten Algorithmus nach
> der Zahlentheorie) sind höchstens gleich 20 hast du oben
> beschrieben.
>  Aber warum sind diese k genau die MAXIMALEN m sodass [mm]p^m \le[/mm]
> 20 wie in Algorithmus 1) beschrieben?

Nun: wenn $m [mm] \in \IN$ [/mm] maximal ist mit [mm] $p^m \le [/mm] 20$, dann gilt:

  1. Ist $a [mm] \in \{ 1, \dots, 20 \}$ [/mm] mit [mm] $p^k \mid [/mm] a$, so muss [mm] $p^\k \le p^m$ [/mm] sein (wegen der Maximalität von $m$) und somit $k [mm] \le [/mm] m$.

  2. [mm] $p^m \in \{ 1, \dots, 20 \}$ [/mm] (also ist [mm] $p^m$ [/mm] tatsächlich Teiler einer Zahl aus dem Bereich).

Damit ist $m$ auch das grösste $m$, für das [mm] $p^m$ [/mm] eine Zahl aus [mm] $\{ 1, \dots, 20 \}$ [/mm] teilt.

LG Felix


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]