Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Primteiler und Primfaktoren zählen...
Druckversion
Druckversion
Antworten
Antworten
Autor
Schule Primteiler und Primfaktoren zählen...
Bekell
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.09.2008
Mitteilungen: 2082
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-09-12


Ich habe jetzt folgende Fnktn geschrieben:
Python
  1. def ermittel_primteiler(x):
  2. primteiler_liste=[]
  3. y=x
  4. #for i in range(3,x//2,2):
  5. for i in range(1,y,1):
  6. if x%i==0 and isprime(i):
  7. primteiler_liste.append(i)
  8. return(primteiler_liste)
Sie funktioniert man kann das y auf x/2 oder sqrt(x) variieren, deswegen die Zeile.

Sie sammelt aber nur die Primteiler. Ich brauche jetzt, daß sie bei 27 drei mal die 3 drin hat. Was kann ich tun, ohne eine weiteres if und eine weitere Schleife einzubauen? Denn die 27 hat drei PF!





-----------------
Das Schwierige ist nicht die Mathematik. Schwierig ist es zu formulieren, daß man selber versteht, was man sieht und die anderen auch!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Quorum
Neu Letzter Besuch: im letzten Monat
Dabei seit: 11.09.2020
Mitteilungen: 4
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-09-12


Hallo Bekell,

ich bin zwar kein Phython-Experte aber zu dem Problem selbst:

Eine einfache Schleife wird da nicht reichen. Die von dir beschriebene Schleife läuft ja nur einmal durch und testet jeweils ein einziges Mal für jedes i in {1, ..., x} ob x ohne Rest durch i teilbar ist und i außerdem eine Primzahl ist.

D.h. dies wird dir nur verschiedene Primteiler liefern.

Es gibt zwei Möglichkeiten dies umzusetzen:
Entweder über eine while-Schleife, wobei die Bedingung solange true ist, wie es noch Teiler zu berechnen gilt.
Oder durch Rekursion, wobei dort der erste Teiler berechnet werden könnte, und dieselbe Funktion dann zur Berechnung der Teiler für den Rest genutzt werden kann.

Ich hoffe das war einigermaßen verständlich!
Grüße



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1645
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-09-12


Am einfachsten ist eben, jede einzelne Zahl zu faktorisieren, N ungerade

countteiler=0
for i=3 TO sqrt(N) Step 2
S: IF N MOD i = 0 THEN countteiler+=1:N=N\i:GOTO S
NEXT i
countteiler+=1

Anders ist das schwer machbar.

Hat man N=1001, dann gibt es 3 Primteiler, würde aber beim schrittweise durchgehen 7,11,13,77,91,...alle zählen, geht also so nicht.

Einzig was ich noch sehe, spanne ein 2D-Feld F(X,2) auf und setze den Feldinhalt auf die Zahl selbst.

F(111,1)=111:F(111,2)=0
...
F(777,1)=777:F(777,2)=0


Wäre der Primteiler 3 dran, und ist F(111,1) MOD 3=0, dann setzen F(111,1)=111\3, zähle Teileranzahl+1 mit F(111,2)+=1

Lasse die 3 xmal durchs Feld, bis eben 3^x>größtes N ist , damit macht der aus 27->9->3->1 und bei 243 eben 5mal. Sollte schneller sein, als jede Zahl einzeln zu faktorisieren. Allgemein gilt für Durchläufe x für Teiler P

x=INT( LOG(N)/LOG(P) )



-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bekell
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.09.2008
Mitteilungen: 2082
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-09-12


Ich danke für die Tips, fahr jetzt baden und mach mich dann an die Arbeit .....


-----------------
Das Schwierige ist nicht die Mathematik. Schwierig ist es zu formulieren, daß man selber versteht, was man sieht und die anderen auch!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3634
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-09-12


Hallo Bekell,

oder ist es das was du suchst: keine loop verwenden, sondern eine while Schleife, und die Schleifenvariable nicht erhöhen, wenn ein Teiler gefunden wurde, um ggf. mehrfaches Vorkommen mit zu erfassen?
python
def liste_der_primteiler(x):
    teiler=[]
    while x%2==0:
        teiler.append(2)
        x=x//2
    y=3
    while y*y<=x:
        if x%y==0 and isprime(y):
            teiler.append(y)
            x=x//y
        else:
            y+=2
    teiler.append(x)
    return teiler


[Die Antwort wurde nach Beitrag No.2 begonnen.]


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-09-12


Will man eine Zahl faktorisieren, so kann man wie folgt vorgehen:
Python
def factorize(N):
    PF = []
    p = 2
    while p*p <=N:
        while N%p==0:
            PF.append(p)
            N//=p
        p = next_prime(p)
    if N>1:
        PF.append(N)
    return PF

Will man alle Zahlen bis zu einer Grenze faktorisieren, so kann man ein Primzahlsieb modifizieren:
Python
def factorize_all(N):
    L = [[n,{}] for n in range(N+1)]
    p = 2
    while p*p<=N:
        e = 1
        while p**e <= N:
            for t in range(p**e,N+1,p**e):
                if not p in L[t][1]:
                    L[t][1][p]=0
                L[t][1][p] += 1
                L[t][0] //= p
            e+=1
        p+=1
        while p*p <= N and L[p][0]<p:
            p+=1
    for n in range(N+1):
        p = L[n][0]
        if p > 1:
            L[n][1][p]=1
            L[n][0] = 1
    return [f for n,f in L]

factorize_all(10) =>  [{}, {}, {2: 1}, {3: 1}, {2: 2}, {5: 1}, {2: 1, 3: 1}, {7: 1}, {2: 3}, {3: 2}, {2: 1, 5: 1}]

factorize(108) =>  [2, 2, 3, 3, 3]

[Die Antwort wurde nach Beitrag No.3 begonnen.]


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bekell hat die Antworten auf ihre/seine Frage gesehen.
Bekell wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]