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 = p₁^e₁ · p₂^e₂ . . . p_n^e_n als Produkt der Primzahlpotenzen heißt kanonische Primfaktorzerlegung von n.

Das Programm zerlegt jede natürliche Zahl n, die kleiner als 10¹⁴ 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

Die ersten 7 vollkommenen Zahlen

                                  6 = 2 · 3
                                28 = 22 · 7
                              496 = 24 · 31
                            8128 = 26 · 127
                    33550336 = 212 · 8191
                8589869056 = 216 · 131071
            137438691328 = 218 · 524287                  

Ergänzung

Statt einer einzelnen Zahl kann auch ein Zahlenintervall oder eine Zahlenfolge in Primfaktoren zerlegt werden. Die Eingabe entspricht dem Programmpunkt  Folgen und Reihen.

Carl Friedrich Gauss (1777−1855) in den Disquisitiones Arithmeticae (1801):
Dass das Problem, die Primzahlen von den zusammengesetzten zu unterscheiden und letztere in ihre Primfaktoren zu zerlegen zu den wichtigsten und nützlichsten der ganzen Arithmetik gehört und den Fleiss und die Weisheit der Geometer der Antike und der Neuzeit beschäftigt hat, ist so bekannt, dass es überflüssig ist, viel darüber zu sagen.

Siehe auch:

Primzahlen
Wikipedia: Primfaktorzerlegung