1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

B Prime Factorization of 5-Digit Numbers

  1. May 29, 2017 #1
    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.
     
  2. jcsd
  3. May 29, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    There is no easy way that works for all numbers. If there is at most one large prime factor, trial division works reasonably well.
     
  4. May 29, 2017 #3
  5. May 29, 2017 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  6. May 30, 2017 #5
    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
     
  7. May 30, 2017 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  8. May 31, 2017 #7
    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,
     
  9. Jun 1, 2017 #8
    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
     
  10. Jun 1, 2017 #9

    symbolipoint

    User Avatar
    Homework Helper
    Education Advisor
    Gold Member

    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.
     
  11. Jun 1, 2017 #10
    Your trick just checks 7,11,13, which are relatively easy to check. Are there any similar tricks for bigger primes?
     
  12. Jun 1, 2017 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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 lets 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
     
  13. Jun 3, 2017 #12
     
  14. Jun 3, 2017 #13
    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...
     
    Last edited: Jun 3, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prime Factorization of 5-Digit Numbers
Loading...