Primfaktorzerlegung

Jede natürliche Zahl n > 1 besitzt eine bis auf die Reihenfolge der Faktoren eindeutige Darstellung als Produkt von Primzahlen. (Fundamentalsatz der Zahlentheorie)

Die eindeutige Darstellung   n = p1e1 · p2e2 . . . pnen als Produkt der Primzahlpotenzen heißt kanonische Primfaktorzerlegung von n.

Das Programm zerlegt jede natürliche Zahl n, die kleiner als 1014 ist, in ihre Primzahlpotenzen.

Beispiele:

  99999999999901 = 19001 · 5262880901
  99999999999001 = 107 · 401 · 1327 · 1756309
  99999999990001 = Primzahl
 
    3938980639167 = 314 · 77
999330136292431 = 999712 · 99991
    1596644705119 = 909091 · 1756309
	
 100000000000027 = 73² · 271 · 751 · 92203	
 100000000000037 = 1858741 · 53799857	
 100000000000047 = 3 · 7 · 83 · 57372346529	
 100000000000057 = 23 · 4347826086959	
 100000000000067 = Primzahl
 100000000000077 = 3 · 17 · 3299 · 594357­
 100000000000087 = 11 · 12647 · 718819411
 100000000000097 = Primzahl
                                11 = Primzahl
                              101 = Primzahl
                            1001 = 7 · 11 · 13
                          10001 = 73 · 137
                        100001 = 11 · 9091
                      1000001 = 101 · 9901
                    10000001 = 11 · 909091
                  100000001 = 17 · 5882353
                1000000001 = 7 · 11 · 13 · 19 · 52579
              10000000001 = 101 · 3541 · 27961
            100000000001 = 112 · 23 · 4093 · 8779
          1000000000001 = 73 · 137 · 99990001
        10000000000001 = 11 · 859 · 1058313049
      100000000000001 = 29 · 101 · 281 · 121499449
    1000000000000001 = 7 · 11 · 13 · 211 · 241 · 2161 · 9091
  10000000000000001 = 353 · 449 · 641 · 1409 · 69857

Siehe auch:

Primzahlen
Wikipedia: Primfaktorzerlegung