Anzahl der (primen) Teiler einer Zahl?

[0001001]

Mal wieder was zahlentheoretisches.
Würde gerne die Teileranzahlfunktion implementieren (Teileranzahlfunktion ? Wikipedia).

Die Teiler einer Zahl zu bestimmen ist trivial. -> Schleife von 2 bis n/2 und prüfen ob die n durch die Zahl teilbar ist.

Bei der Teileranzahlfunktion stehen mir allerdings zwei Probleme im Weg.
Zum einen muss ich ja prüfen ob ein Teiler prim ist, oder ob der Teiler selbst Teiler enthält. Zum anderen würde dies ja eine Rekursion zur Folge haben.

Zur Veranschaulichung ein kleines Beispiel:
n = 16

16 ist teilbar durch, 2,4,8
wobei 4 als 2^2 und 8 als 2^3 geschrieben werden kann.
Demnach hat 16 einen primen Teiler, nämlich 2. (2^4). Der Wert der Teileranzahlfunktion d(n) wäre demnach 3, da dort 1 und n auch als Zeiler gesehen werden.

Kann mir jemand helfen, die Funktion in Java zu implementieren?

 

[SlaterB]

wenn du einen Teiler gefunden hast, denn dividiere die Ursprungszahl so oft durch den Teiler, wie möglich,

Beispiel:
16, Teiler 2, 16 so oft wie möglich teilen, hier bis 1, fertig,

hat den Vorteil, dass die verkleinerte Zahl dann nicht mehr durch 4 teilbar ist,
und noch besser: nach 2 bist du hier schon fertig, musst nicht noch bis 16 hoch gehen,

anderes Beispiel 145945,
erster Teiler 5 -> 29189,
zweiter Teiler 17, 2x drin -> 101
dritter Teiler 101, fertig

so musst du nicht hundertausende Teiler testen, sondern nur bis zum maximalen Primteiler,
und Mischteiler wie 5*7 = 35 machen dir auch keinen Ärger

----

weitere Optimierung: man muss generell nur bis zur Wurzel des Maximums suchen,
wenn nach Teiler 17 nur noch ein Rest 101 übrig bleibt,
dann bist du schon fertig, es kann für 101 keinen Teiler größer Wurzel(101) ~ 10 geben,
denn wenn es einen derart großen Teiler gäbe, z.B. 20, dann stände dem eine kleine Gegenzahl gegenüber (100/20 = 5), und die kleinen Zahlen wurden ja schon getestet, 101 ist nicht durch 5 teilbar


für 145945 nur 17x auf Teilbarkeit prüfen, das klingt doch nicht schlecht

 

[0001001]

Danke SlaterB für die ausführliche Antwort.

Eine Frage noch dazu:
Bei der Überprüfung muss ich nur auf Teilbarkeit durch Primzahlen prüfen, also ob n durch 2,3,5,7,11,13,17, ... teilbar ist, richtig?

 

[SlaterB]

stimmt,
so gesehen könnten auch alle anderen gesagten Dinge wegfallen,
denn wenn du nur durch die Liste der Primzahlen prüfst, kommt für 16 die 4 und 8 ja nicht in Frage

aber das Verkleinern verringert die maximale Suchtiefe

 

[Leroy42]

FALSCH!

Jeder Teiler zählt.
Nach Wikipedia:

d(n) = tau(n) = #{d : 1 <= d <= n und d|n}

(Auch gleich des Produkts der um 1 erhöhten Exponenten der Primfaktorzerlegung von n)

 

[Leroy42]

Da wird's ja wieder Zeit für mein genial effizientes Primzahl-Programm

public class Primzahlen {
	static long aufrufe;
	
	public static boolean isPrim(int n) {
		++aufrufe;
		if (n<2) 
			return false; 
		int anzTeiler = 0; 
		for (int kandidat=2; kandidat < n; kandidat++) 
			if (isPrim(kandidat) && n%kandidat == 0) 
				++anzTeiler; 
		return anzTeiler == 0; 
	}	
	
	public static int d(int n) {
		int sum=0;
		for (int i=1; i <= n; i++)
			if (isPrim(i) && n%i == 0)
				sum += i;
		return sum;
	}
	
	public static void main(String[] args) {
		long time = System.currentTimeMillis();
		System.out.println("d(30)="+d(30) +" (geschmeidige " +aufrufe + " Aufrufe) : Zeit in ms:"+(System.currentTimeMillis()-time));
	}
}

Ausgabe:

d(30)=10 (geschmeidige 536870912 Aufrufe) : Zeit in ms:23594

:shock:

 

[Jango]

Du bist eben einfach genial, lieber Th.