# UVa 583

## Explanation

While a completely dumb approach to factoring a number ${\displaystyle n}$ is to try dividing by all possible factors ${\displaystyle f}$ in the range ${\displaystyle 2\leq f\leq n-1}$ and checking their remainder, this will timeout. However, a slightly smarter approaching, trying all factors f in the range ${\displaystyle 2\leq f\leq {\sqrt {n}}}$ will run in time.

The reason checking the reduced set of candidates works is essentially that the smaller factor is never bigger than ${\displaystyle {\sqrt {n}}}$, a very short proof follows.

Consider a positive integer ${\displaystyle n}$ with positive factors ${\displaystyle a}$ and ${\displaystyle b}$, so ${\displaystyle n=a\times b}$. Without loss of generality, choose to label the smaller number ${\displaystyle a}$. So then ${\displaystyle a\leq b}$, and ${\displaystyle a\times a\leq a\times b\leq n}$, and therefore ${\displaystyle a\leq {\sqrt {n}}}$.

## Gotcha's

Negative numbers are allowed, negate the input and remember the -1 coefficient before factoring.

## Optimizations

These are not neccesary but will give you a faster time. The first optimization is simple, 2 is the only even prime, so after two, we can check only odd factors, which will reduce the possible factor space by a factor of 2, and give a nearly equal speed up.

An optimization that is a bit harder to implement is to pre-compute all the primes ${\displaystyle p}$ in the range ${\displaystyle 2\leq p\leq {\sqrt {2^{31}}}}$ with the Prime Sieve of Eratosthenes and use that as the candidate list.

There are only about ~5,000 primes from ${\displaystyle 2\leq p\leq {\sqrt {2^{31}}}}$ the time that it takes to generate all these primes are not as significant as making your program as optimized as possible on output.

• Store the result in a string. (will save most of your time) output takes a long time.
• While the number you are working with is not 1.

## Input

-190
-191
-192
-193
-194
195
196
197
198
199
200
15152412
634637
12341
7
43
27724
0


## Output

-190 = -1 x 2 x 5 x 19
-191 = -1 x 191
-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3
-193 = -1 x 193
-194 = -1 x 2 x 97
195 = 3 x 5 x 13
196 = 2 x 2 x 7 x 7
197 = 197
198 = 2 x 3 x 3 x 11
199 = 199
200 = 2 x 2 x 2 x 5 x 5
15152412 = 2 x 2 x 3 x 11 x 191 x 601
634637 = 43 x 14759
12341 = 7 x 41 x 43
7 = 7
43 = 43
27724 = 2 x 2 x 29 x 239