kgV,Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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
|
|
| |
|
> 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.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
|
