Getting factors of a number.

Rhino

Sorry, I don't know correct terminology. But how do you get the square or factors of a number.


For example: 81 is 9x9. I only know that because I memorized the multiplication tables. But how would I do it by hand if I didn't know? What's this called, square rooting a number? Factoring a number?

Captain Vash

if you're looking at

X = YxY

and you want to know what Y is equal to for a given value of X, then yes, you are looking for the Square Root of X.

admanb

If you're trying to find all the factors of a number, 81 is 3*3*3*3. There are a few tricks: if the number's even, divide by two (duh), if the digits of the number add up to a number divisible by three, divide by three, if it ends in five, divide by five. If that doesn't simplify it enough for you to find the rest of the factors, write a function in a scripting language to do it for you. :P

Metalbourne

I was taught how to do this in grade school, but have forgotten since then.

Here's something I found on google

Thanatos

I think guess-and-check or "use a calculator" are your options. Though, it's easier if you prime factor a number before you guess-and-check.

You can prime factor a number (break it down to its constituent prime numbers). This is usually done by guess-and-check, starting with your smallest numbers first. So, if I wanted to know what the prime factors of 9756 are, the easiest way to start is by dividing by two or three. We know it's both even (because it ends in an even number) and divisible by three (since the sum of the digits is divisible by three). So, we start by dividing by two (and we get 2 * 4878), then dividing by 3 (2 * 3 * 1626). Still divisable by both two and three, so we get (2 * 2 * 3 * 3 *271). 271 is not divisible by two or three, obviously not divisible by 5, not divisible by 7 (easiest way to figure that out is to know that 7 * 4 = 28, therefore 280 is a multiple of 7, therefore 271 isn't). 260 isn't a multiple of 11, so 271 isn't, either. Not a multiple of 13, and 17 * 17 is greater than 271, (it's 289), so 271 must be prime. Since we can't split the prime factors in half symmetrically, we know that 9756 is not a square number.

Hirocon

I'd just like to add that there is no known efficient algorithm for factoring large numbers. The search for an efficient factoring algorithm is an important unsolved problem in computer science. Even so, it's not too difficult to factor small numbers by brute force. Just divide by 2 as many times as you can, then by 3, then by 5, then 7, 11, etc.

musanman

Pretty sure this is one of the reasons we need Riemann's solved...because we can't really do it without brute force.

ceres

I just learned how to do this by iteration, but it can take quite a long time.

SanderJK

Yeah, it can only be done by brute force. There's a reason it's used as a basis for encryption. The basis is that every number is a multiplication of only prime numbers. The fastest way to get these is to just divide by all the prime numbers (2, 3, 5, 7, 11, 13 etcet).