Seite 1 von 1
Primfaktorzerlegung
Verfasst: Donnerstag 26. November 2015, 21:44
von Chemical Bro
Hallo!
Ich habe folgenden Code geschrieben:
Code: Alles auswählen
import math
a = 0
while a == 0:
b = int(input())
liste = []
string = ''
if b < 4:
c = b
else:
c = math.floor(b**0.5)+1
for i in range(2,c):
liste.append(i)
for i in range(len(liste)):
while b%liste[i] == 0:
string += str(liste[i])
b /= liste[i]
string += ','
if b > 1:
string += str(b)
else:
string = string[:-1]
print(string)
Dieser gibt mir die Primfaktorzerlegung einer Zahl aus.
Manchmal ist aber die letzte Zahl dieser Zerlegung ein float,
was mir aber ganz und gar nicht gefällt.
Z.B. bei 11111 gibt er mir 41,271.0 aus
oder bei 1111111111: 11,41,271,9091
also ohne .0
Kann mir jemand erklären, warum er bei manchen Zahlen die letzte Zahl als float behandelt,
bei manchen aber nicht und wie man das vermeiden kann?
Re: Primfaktorzerlegung
Verfasst: Donnerstag 26. November 2015, 22:05
von Sirius3
@Chemical Bro: wenn a immer 0 ist, kannst Du auch gleich "while True:" schreiben. Warum behandelst Du b<4 als Sonderfall? Die Liste liste ist ziemlich überflüssig, da sie nur die Zahlen enthält die Du über range auch direkt iterieren kannst. Statt Strings nacheinander mit + zusammenzustückeln sammelt man sie normalerweise in einer Liste und fügt sie zum Schluß per join zusammen. Wenn Du Ganzzahlen willst, solltest Du auch Ganzzahldivision // benutzen.
Re: Primfaktorzerlegung
Verfasst: Donnerstag 26. November 2015, 22:21
von Chemical Bro
Sirius3 hat geschrieben:@Chemical Bro: wenn a immer 0 ist, kannst Du auch gleich "while True:" schreiben. Warum behandelst Du b<4 als Sonderfall? Die Liste liste ist ziemlich überflüssig, da sie nur die Zahlen enthält die Du über range auch direkt iterieren kannst. Statt Strings nacheinander mit + zusammenzustückeln sammelt man sie normalerweise in einer Liste und fügt sie zum Schluß per join zusammen. Wenn Du Ganzzahlen willst, solltest Du auch Ganzzahldivision // benutzen.
Hat funktioniert. Danke sehr!
Re: Primfaktorzerlegung
Verfasst: Donnerstag 26. November 2015, 22:27
von Chemical Bro
Code: Alles auswählen
import math
while True:
b = int(input())
liste = []
c = math.floor(b**0.5)+1
for i in range(2,c):
while b%i == 0:
liste.append(str(i))
liste.append(',')
b //= i
string = ''.join(liste)
if b > 1:
string += str(b)
else:
string = string[:-1]
print(string)
Meint ihr die kann man laufzeittechnisch noch verbessern?
EDIT: Gehört zwar nicht dazu, aber ich hab gerade herausgefunden, dass 1.111.111.111.111.111.111 eine Primzahl ist
geil, oder?
und 11.111.111.111.111.111.111.111 auch
, aber bis 100 Einsen hintereinander nur 11 (2 Einsen).
Re: Primfaktorzerlegung
Verfasst: Donnerstag 26. November 2015, 22:49
von Sirius3
@Chemical Bro: ein Verdopplung der Geschwindigkeit ist ohne große Mühe machbar. Du solltest Dir nochmal join genauer anschauen.
Re: Primfaktorzerlegung
Verfasst: Donnerstag 26. November 2015, 22:55
von Chemical Bro
Sirius3 hat geschrieben:@Chemical Bro: ein Verdopplung der Geschwindigkeit ist ohne große Mühe machbar. Du solltest Dir nochmal join genauer anschauen.
Hmm, ich gucke, aber ich weiß es nicht.
Wie genau?
Re: Primfaktorzerlegung
Verfasst: Donnerstag 26. November 2015, 23:00
von BlackJack
@Chemical Bro: Wieviele *gerade* Primzahlen gibt es denn?
Re: Primfaktorzerlegung
Verfasst: Donnerstag 26. November 2015, 23:14
von Chemical Bro
BlackJack hat geschrieben:@Chemical Bro: Wieviele *gerade* Primzahlen gibt es denn?
Es gibt (Achtung Wortspiel) gerade 1 gerade Primzahl.
Aah ja. Ich werd mir das mal überlegen.
Aber was das jetzt mit join zu tun hat... :K
Re: Primfaktorzerlegung
Verfasst: Donnerstag 26. November 2015, 23:24
von BlackJack
@Chemical Bro: *Das* hat nichts mit dem `join()` zu tun. Das solltest Du Dir unabhängig davon mal ansehen, denn Du verwendest das ”falsch”, also zumindest sehr ungünstig. Tipp: Die Kommas haben nichts in der Liste zu suchen!
Re: Primfaktorzerlegung
Verfasst: Freitag 27. November 2015, 15:51
von Chemical Bro
BlackJack hat geschrieben:Tipp: Die Kommas haben nichts in der Liste zu suchen!
Doch, der besseren Uebersichtlichkeit halber.
Re: Primfaktorzerlegung
Verfasst: Freitag 27. November 2015, 16:26
von pillmuncher
Chemical Bro hat geschrieben:BlackJack hat geschrieben:Tipp: Die Kommas haben nichts in der Liste zu suchen!
Doch, der besseren Uebersichtlichkeit halber.
Nein, falsch. Guckstu:
Code: Alles auswählen
In [1]: ', '.join(['1', '2', '3', '4', '5'])
Out[1]: '1, 2, 3, 4, 5'
Re: Primfaktorzerlegung
Verfasst: Freitag 27. November 2015, 16:33
von Chemical Bro
O.K.
Re: Primfaktorzerlegung
Verfasst: Freitag 27. November 2015, 22:02
von Chemical Bro
(Nur ein Teil des Codes!)
Code: Alles auswählen
for i in range(7,b,2):
if i%3!=0 and i%5!=0:
while a%i == 0:
liste.append(str(i))
a //= i
if a == 1:
break
if a > 1:
liste.append(str(a))
string = ','.join(ende)
print(string)
Ich hab ja jetzt z.B. für 372678376272 als Ausgabe 2,2,2,2,3,23,3617,93329.
Manchmal hat man aber Pech und man hat z.B. 3^70 oder (2^25)*(7^13) o.ä. erwischt und er gibt 3,3,3,3, usw. aus,
was ziemlich unübersichtlich ist.
Ich will daher sowas wie 2^10,3^4,5^2,7,11,13 haben,
also bei allen PF(Primfaktoren) > 1 ^n stehen haben(n Anzahl der PF).
Mir ist klar, dass ich das über die
Liste mit count machen muss,(oder doch nicht?)
wie genau kann ich jetzt aber alle Listenelemente
desselben Inhalts durch k^n ersetzen(n>1)?
Re: Primfaktorzerlegung
Verfasst: Freitag 27. November 2015, 23:34
von Chemical Bro
Chemical Bro hat geschrieben:(Nur ein Teil des Codes!)
Code: Alles auswählen
for i in range(7,b,2):
if i%3!=0 and i%5!=0:
while a%i == 0:
liste.append(str(i))
a //= i
if a == 1:
break
if a > 1:
liste.append(str(a))
string = ','.join(liste)
print(string)
Ich hab ja jetzt z.B. für 372678376272 als Ausgabe 2,2,2,2,3,23,3617,93329.
Manchmal hat man aber Pech und man hat z.B. 3^70 oder (2^25)*(7^13) o.ä. erwischt und er gibt 3,3,3,3, usw. aus,
was ziemlich unübersichtlich ist.
Ich will daher sowas wie 2^10,3^4,5^2,7,11,13 haben,
also bei allen PF(Primfaktoren) > 1 ^n stehen haben(n Anzahl der PF).
Mir ist klar, dass ich das über die
Liste mit count machen muss,(oder doch nicht?)
wie genau kann ich jetzt aber alle Listenelemente
desselben Inhalts durch k^n ersetzen(n>1)?
Re: Primfaktorzerlegung
Verfasst: Freitag 27. November 2015, 23:59
von BlackJack
@Chemical Bro: Statt in jedem Schleifendurchlauf den Teiler hinzuzufügen müsstest Du halt einen Zähler erhöhen und den dann am Ende hinzufügen, zusammen mit dem Teiler. Also falls der Zähler >0 ist.