## Prime Factorization

The program factorizes natural numbers into their prime powers.

The prime factorization or canonical representation of a number is
unique except for the order of the factors.

### Examples:

99999999999901 = 19001 · 5262880901
99999999999001 = 107 · 401 · 1327 · 1756309
99999999990001 = Prime number
3938980639167 = 3^{14} · 7^{7}
999330136292431 = 99971^{2} · 99991
1596644705119 = 909091 · 1756309
100000000000027 = 73² · 271 · 751 · 92203
100000000000037 = 1858741 · 53799857
100000000000047 = 3 · 7 · 83 · 57372346529
100000000000057 = 23 · 4347826086959
100000000000067 = Prime number
100000000000077 = 3 · 17 · 3299 · 594357
100000000000087 = 11 · 12647 · 718819411
100000000000097 = Prime number

11 = Prime number
101 = Prime number
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 = 11^{2} · 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

### Complement

Instead of a single number, an interval or a sequence of numbers can also be broken down into prime factors. The input is identical to the program item *Sequences and Series*.

*Carl Friedrich Gauss (1777-1855) in the Disquisitiones Arithmeticae (1801):*

It is so well known that the problem of distinguishing between the prime numbers and the composite numbers and of breaking them down into their prime factors is one of the most important and useful in all of arithmetic, and has preoccupied the diligence and wisdom of the ancient and modern geometers that there is no need to say a lot about it.

### See also:

Prime Numbers
Wikipedia: Fundamental theorem of arithmetic