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!

Prime factoring stupid question

  1. Jan 1, 2014 #1
    trust me this is trivial...
    As a kid I had a teacher fond of asking if numbers were prime. Of course at the time I had no calculator and did not have many primes remembered. I did not even know the less than square root.
    I came up with a method that made a simple chart of smaller than the original number to use.

    I am wondering what this is called. Simple I would dived an odd number by 2.

    and take the higher and lower number. Say for 35 this would be 17, 18.

    Take 17: 17,16,15,14,13, and so on..
    (17,1), start. (16,3), (15,5), (14,7), (13,11), (12,15) No need to go further. this provided me with a simple set with the odds to try and divide by, and only the factors of the original odd number are divisible such as 5, and 7 to whole numbers. A simple test was to subtract the number that was dividable from the start number, (17-15=2) and add it to the other paired number (18+2= 20)
    and of course divide it by the same number in this case 5.

    Note: this can be done from the number -1 down also. Faster from the bottom. With (34,1), (33,2) and so on.

    Of course this is just division by the odd numbers, yet I have not seen the use of the split.
    I did use it for factoring of other numbers also. It was fast.

    Any one know what this is called??
  2. jcsd
  3. Jan 1, 2014 #2


    Staff: Mentor

  4. Jan 1, 2014 #3
    Usually you can also do test by divisibility for small prime numbers, whether a number is divisible by 2, 3, 5, 7, 11. The goal is not to divide them but to test whether they can be divided.

    Trivial example without knowing 9x3=27.
    9/3 = 3, so 27 is divisible by 3.


    Other than that if you can remember 1-10 or even further multiplication table, you will know what numbers are divisible by what rather quickly without doing computation. This is what most students in my school are taught with.
  5. Jan 1, 2014 #4
    Well this was just some thing a small child learned a long time ago. 40 years +..


    It uses a number less than half the original.

    Thanks for looking, was just wondering if such had a name.

    edited due to this "This routine consists of dividing n by each integer m that is greater than 1 and less than or equal to the square root of n." From the above link.
    It would fall under a methodical up the line from 1 of the evens.
    Yet I have not found reference to splitting the number to do so..
    Last edited: Jan 1, 2014
  6. Jan 1, 2014 #5


    User Avatar
    Science Advisor

    You don't need all of those. since 35 is, as you said, odd, you really only need to check odd numbers. But why are you pairing the numbers with "1", "3"? You really just need to check 17, 15, 13, 7, 5, 3. And then, of course, you would find that 35= (17)(5). But simpler, I think, is the "usual" way: 35 is odd so is not divisible by 2, 3 divides into 35 11 times with remainder 2 so is not divisible by 3 (even simpler: 3+ 5= 8 which is not divisible by 3 so 35 is not divisible by 3), 5 divides into 35 7 times with no remainder. 5 and 7 are both prime so 35= (5)(7).

  7. Jan 1, 2014 #6
    35 was a simple number easily factored even as a kid. It was an example.

    Again thanks for the time.
  8. Jan 1, 2014 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    It also helps to remember basic decimal integer facts:
    Any even integer > 2 is not prime
    Any integer > 5 which ends in a 0 or a 5 is not prime (the integer will obviously have 5 as a factor)
    Any integer > 3, if all of the digits of an integer sum to 3 or a multiple of 3, that integer is divisible by 3, and is not a prime
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook