Efficient Prime Factoring Method for Numbers Below the Square Root"

[lostcauses10x]

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??

 

[jedishrfu]

solution by trial and error?

Normally prime numbers are tested using trial division:

http://en.wikipedia.org/wiki/Prime_number

 

[Seydlitz]

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.
27?
2+7=9
9/3 = 3, so 27 is divisible by 3.

http://en.wikipedia.org/wiki/Divisibility_rule

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.

 

[lostcauses10x]

Well this was just some thing a small child learned a long time ago. 40 years +..

removed.

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..

 

[HallsofIvy]

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)

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).

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??

 

[lostcauses10x]

35 was a simple number easily factored even as a kid. It was an example.

Again thanks for the time.

 

[SteamKing]

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