I had some time to sit down with a pen and paper to figure out a better way of getting all the divisors out of a number.
I don't think there are any clever tricks using recursion I can use. I went down that path because it worked for something else but I don't think it will work here.
This makes sense in hindsight (and it's a testament to how poor at basic arithmetic I am) that I only need to test to half the number.
For example, the number 90 has 10 divisors: 1, 2, 3, 5, 9, 10, 18, 30, 45, 90. Obviously I don't need to test beyond half the number (which holds true for odd numbers, too).
I might have even stumbled upon a way of detecting square numbers.
64's divisors are 1, 2, 8, 16, 32, 64. If you see the symmetry in both 90 and 64's divisors you can see a pattern.
90: 1,2,3,5,9,10,18,30,45,90
Taking the outer numbers and working out way pairwise inward we have:
(1,90)(2,45)(3,30)(5,18)(9,10)
These are factors of 90.
64:1,2,4,8,16,32,64
Doing the same thing we find a slight difference - there are an odd number of divisors.
(1,64)(2,32)(4,16)(8,?)
We of course know that 8*8 is 64. This makes me wonder if all squares have an odd number of divisors, or if there are number with an odd number of divisors that
aren't squares.
25 is a square and has an odd number: 1,5,25
So, just some thoughts. I could quickly spin off my program to test for stuff like that.
Anyways I can quickly change my program to only loop n mod x and test for 0 such that x only goes to half of n instead of all the way up to n.
No comments:
Post a Comment