# Prime factor calcuation

• Mar 15th 2010, 07:33 PM
studentme
Prime factor calcuation
Hi, I calculated the prime factors of the following numbers:

1. 3211
13*13*19

2. 310
2*5*31

3. 4139
This is prime number

I took me a few calculations to reach the answers - I usually start with the lowest prime number and use division, is there any way to use fewer calculations?
• Mar 15th 2010, 07:41 PM
Bacterius
Ah, factorizing numbers quickly is considered like a very, very hard problem indeed. For mental calculation I think there is nothing more effective than checking division with every prime number up to $\sqrt{n}$ where $n$ is the number to factorize. However you could maybe spend a couple of seconds looking at the number before and trying to see if it doesn't have some particular structure (like an obvious multiple of $11$), etc ... You might also like to do it the other way round : start at $\sqrt{n}$ and go down until you reach $1$, it can reveal useful if the number has only two prime factors that are near each other.

This is for mental calculation ; for computer calculation there are much, much more effective methods going around, that would crunch most numbers you could ever think of. But they can get quite complicated to understand if you are not familiar with algorithms.