Prime Factorization of 5-Digit Numbers

[itsabdulbasit]

Hi,

Can anyone please tell me any easy way of prime factorizing 5-digit composite numbers from 10,000 to 99,999 with little writing or mentally?

Thanks.

 

[mfb]

There is no easy way that works for all numbers. If there is at most one large prime factor, trial division works reasonably well.

 

[willem2]

Just the first 5 pages or so should be enough.
Trial division is probably the fastest for numbers of this size. at most 65 tries.

 

[mfb]

at most 65 tries.

And each one is like "check if 61351 is divisibly by 17". Possible: sure, even mentally. The fastest approach: Yes. Fast? Well...
75% of all numbers are divisible by 2, 3, 5 or 11, where the checks are easy, but then you are still left with the rest.

 

[Janosh89]

you could use a loop type program, eliminate composite numbers of 3 in one program line first;
Then given that all remaining possible factors - if you are considering odd numbers only-
are of the form 6n +/- 1
write ascending "loop" to test factors 7,13,19,(25),31,etc
descending "loop" " " " 6*INT (sqr Z/6)-1 where Z is the candidate (odd) number above your 10 000
and sqr Z /6 is (Z ^ 1/2)/6
Prime numbers will drop out, through this sieve or loop structure when the descending loop reaches, through iterations of -6 , the value of -1

 

[mfb]

Trial division with ascending factors is faster, as smaller numbers are more likely to be factors, but if you do it without a computer you certainly don't want to test all the numbers that are not primes.

 

[ddddd28]

You could possibly compute the square root of your number. At least one prime factor of that number is smaller than the root.
Since you want to find the prime factors for 5 digits numbers, your biggest root will be √99,999= 316.22 - not a big deal because:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 ...
There are only 65 prime numbers less than 316.22.
If you are lucky and your number ends up with 2, you will have to check only about √45000=212.1 ⇒47 numbers.
and if the number ends with 5, so just 34 numbers.
This method is not the most sophisticated one or efficient, but I believe it will be useful for your purposes.
-------------------------------------------------------------------------
For example: 61351
√61351=247 ⇒53 numbers to check...
not dividing: 2,3,5, 7,11,13,17,
dividing: 19
61351/19=3229
√3229=56.8⇒16 numbers to check, however we don't need to check 2,3,5, 7,11,13,17,
not dividing: 19 23 29
31 37 41 43 47 53
therefore: 19*3229=61351
Of course, doing the long divisions by hand is not recommended.
I was lucky of choosing this number as said mfb,

If there is at most one large prime factor, trial division works reasonably well.

 

[Janosh89]

Since in the decimal system, 1001 =7x11x13,
divide your 5-digit number from the right in lots of 3 digits (Po) so that ,say, 16901 gives you 16 / 901
do the simple sum 901-16 (Po-P1)

to give 885 which is indivisible by 7,11, or 13 so that 16901 does not have those particular factors. This will work for any length of decimal number providing you mark off groups of three digits from the right-
Po,P1,P2 ... successively and use the method Po -P1+P2--P3 (even P ,including Po, are positive)
For example 47411 gives 411 -47 =364 so that since 364 is divisible by 7 ,and also 13 ,
47411 is divisible by 7 and 13

 

[symbolipoint]

Make a computer program to do it. This can be a good beginner programming exercise, not requiring too much mathematical knowledge. You might look for a way to create code to run through Sieve Of Eratosthenes process. I've done this a couple of times as a computer program in a form of BASIC.

 

[ddddd28]

Since in the decimal system, 1001 =7x11x13,
divide your 5-digit number from the right in lots of 3 digits (Po) so that ,say, 16901 gives you 16 / 901
do the simple sum 901-16 (Po-P1)

to give 885 which is indivisible by 7,11, or 13 so that 16901 does not have those particular factors. This will work for any length of decimal number providing you mark off groups of three digits from the right-
Po,P1,P2 ... successively and use the method Po -P1+P2--P3 (even P ,including Po, are positive)
For example 47411 gives 411 -47 =364 so that since 364 is divisible by 7 ,and also 13 ,
47411 is divisible by 7 and 13

Your trick just checks 7,11,13, which are relatively easy to check. Are there any similar tricks for bigger primes?

 

[mfb]

11 is easy to check with the alternating sum (add digits in odd places, add digits in even places, the two sums have to differ by a multiple of 11 for divisibility)
101 as prime is easy to check with a similar approach.
999 = 27*37 helps with 37.
9999=9*11*101 doesn't help.
10001 = 73*137 let's you get rid of the first digit quickly for these two primes.
99999 = 9*41*271 if you subtract your number from 99999.
100001 = 11*9091 doesn't help

 

[Janosh89]

Make a computer program to do it. This can be a good beginner programming exercise, not requiring too much mathematical knowledge. You might look for a way to create code to run through Sieve Of Eratosthenes process. I've done this a couple of times as a computer program in a form of BASIC.

 

[Janosh89]

Thanks for your input+reply,symbolipoint! I have a program in that Computer language from quite a few years ago. It also tabulates the primes in non-euclidean and euclidean columns. 12x +1 ,+5 , +7 , and +11
Pity Microsoft has done away with pre-installed Q. Basic.
I would like to share it more widely as it could enthuse/ encourage/ inspire at the elementary or basic level.
My (home) broadband is to be fixed midweek. Let's keep in contact. Someone has done in my Chrome on this Android tablet...