Primfaktorzerlegung

[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?

[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.

[Chemical Bro]

@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!

[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).

[Sirius3]

@Chemical Bro: ein Verdopplung der Geschwindigkeit ist ohne große Mühe machbar. Du solltest Dir nochmal join genauer anschauen.

[Chemical Bro]

@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?

[BlackJack]

@Chemical Bro: Wieviele *gerade* Primzahlen gibt es denn?

[Chemical Bro]

@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

[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!

[Chemical Bro]

Tipp: Die Kommas haben nichts in der Liste zu suchen!

Doch, der besseren Uebersichtlichkeit halber.

[pillmuncher]

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'

[Chemical Bro]

O.K.

[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)?

[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(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)?

[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.