![](https://www.angelfire.com/journal2/ulillillia/images/bigmultiply.png)
Is there a quick way to find factors of a number?
type: trick and shortcut
reliability:
- medium-high
understandability:
- medium
time saving:
- small gain
usefulness:
- medium
difficulty:
- easy-medium
required skill:
- intermediate
overall: 35 of 48 points, ![](https://www.angelfire.com/journal2/ulillillia/images/level7star.gif)
1. Determining divisibility
Consider this question:
List all denominators a fraction with a denominator of 3000 would have, when reduced.
This may sound hard, but there's a way to guarentee that you can find them all. Start with the lowest prime number, 2. Since the last digit is an even number, it is divisible by two. Take 3000 and divide by two:
1500
2|3000
3000
0
Since two is already a factor, then you can use 1500.
Now check for three. To find three, add the digits of the number together. If the added values add to a multiple of 3, in which 3+0+0+0=3, 3000 is a multiple of 3. You'd get 1000 as the other number. For 4, you check to see if the last two digits, the ones and the tens, are a multiple of 4. If it ended in, for example, 1368, it would be based on 68, and 68 is a multiple of 4. If it was 3754, it wouldn't be as 54÷4=13.5, which means it doesn't come out evenly. 3000 is a multiple of 4 as 0 is a multiple of four. Doing the division, you get 750. For five, which should be easy, the number should end in either a 5 or a 0. 3000 ends in a zero so it is a multiple of 5. 600 is the other number. Now, for multiples of six, you'd apply the same principal as 3, except the number must be even. 3000 is a multiple of 3, and it is even, so it is a multiple of 6. 500 is the other number. 7 is a real challenge. I don't know of a trick to tell if a number is a multiple of 7 or not. However, if you divide it, it doesn't come out evenly:
428r4
7|3000
2800
200
140
60
56
4
3000 is not a multiple of 7, thus it wouldn't be a multiple of anything else based on that. For 8 though, it does. To find multiples of 8, the last 3 digits must be a multiple of 8. 0 is a multiple of 8 so it is good. 375 is the other number you get when you divide.
To find multiples of 9, Do the same as you did for 3's, except the sum should be a multiple of 9. 3 is not a multiple of 9, thus 3000 isn't a multiple of 9. For ten, in which you should know, the last digit must be a zero. 300 is the other one. For 11, I haven't figured it out yet. I've found a way for numbers less than 1000, however. You know that 11×11=121, right? The trick is two steps. First, take the hundreds and the tens and find the previous multiple of 110. In this case it's 110 itself. Then, you add 11 to the tens and ones. For a number like 693, you'd consider 660. Then count by 11's [or add 1 to the tens and 1 to the ones until you reach it. Beyond 1000, it gets more difficult. 3000 wouldn't be though as 2200 would be the base and you'd count to 2970, but then 2981, 2992, 3003.... It doesn't come out. For 12, it must meet two conditions: the last two digits are a multple of 4 and the digits add up to a multiple of 3. 3000 meets both so it is a multiple of 12. The other number is 250. There's no known strategy for screwball 13, but apply the same method as 11, only a bit different way. Since 14 is a multiple of 7 and 3000 isn't a multiple of 7, 14 definitely wouldn't go in. 15 works under the following conditions: digits add up to a multiple of 3 and the last digit must be either a 5 or a 0. 3000 meets both. 200. This just continues on until you come to the square root of the number. For the complete list, the answer to the question in focus would be:
1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 25, 30, 40, 50,
60, 75, 100, 120, 125, 150, 200, 250, 300, 375, 500, 600, 750, 1000, 1500, 3000
Yow! 3000 has a ton of factors! Note: I split the list in two groups. The last on the top is where you would not get anything new.
2. An even faster way
There's an even faster way to find all the factors! Consider 3000 again. Divide it by 2 if possible. 1500. If it divides evenly, keep repeating until you get a fraction: 750, 375 187.5. Ignore the fraction one and stop where you last had an even number, 375. Now divide by 3 in the same fashion. 125, 41.66666.... Stop at 125. Next, skip 4 as four is not a prime number, and go to 5 and repeat: 25, 5, 1, .2. Once a value ends in 1, you've found all prime factors. Just multiply these to get all of your divisibilities. The list is 2, 2, 2, 3, 5, 5, then another 5. Let's try a much more complex number: 2339. It's not an even number so don't consider 2. It doesn't end in 5 or 0 so it's not a 5 eihter. The digits add up to 17, not a multiple of 3. The next prime number is 7. Doing the division, it doens't come out. 9 has 2 3's, so it's not prime but 11 is. Though 11 won't divide evenly, so you continue to 13, then 17, 19, 23, etc.. When you divide by about 47, and still haven't taken anything out of it, and if the next prime number, 53, crosses over your last result, you don't need to continue. If this happens, you've found a prime number.
3. List of HUGE prime numbers
I've got quite a list of prime numbers, even some 6-digit and 7-digit prime numbers following this method! The prime numbers above 20,000 required the help of MSWorks spreadsheet to get them for sure. Here's the list of big ones I've found:
5 digits:
11903
15427
17159
17317
20903
29063
41341
44029
53017
60923
72973
6 digits:
129841
150301
173273
219851
313931
407347
408071
683911
766229
819583
888271
922667
7 digits:
1584227
2126029
2509777
These are actual prime numbers that I've got from playing the game "factors" that I so enjoy*.
Footnotes:
* This game features what is described in section 2 above. This game is easy to play, and you can learn how here.