## Prime Factorization

Every natural number n > 1 has a unique representation as a product of prime numbers, except for the order of the factors. (Fundamental theorem of number theory)

The representation n = p_{1}^{e1} · p_{2}^{e2} . . . p_{n}^{en}
as the product of the prime powers is called the canonical prime factorization.

The program factorizes natural numbers smaller than 10^{14} to their prime powers.

### 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

### The first 7 perfect numbers

6 = 2 · 3 28 = 2^{2}· 7 496 = 2^{4}· 31 8128 = 2^{6}· 127 33550336 = 2^{12}· 8191 8589869056 = 2^{16}· 131071 137438691328 = 2^{18}· 524287

### Supplement

Instead of a single number, you can also factorize an interval or a sequence of numbers. The input is identical to that of the
** Sequences and Series** program.

*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 arithmetic, and has occupied the diligence and wisdom of
the ancient and modern geometers that there is no need to say much about it.*

### See also:

Prime NumbersWikipedia: Fundamental theorem of arithmetic