Programming Forums > Application Development > Software Design and Algorithms

titaniumdecoy · Apr 27th, 2006, 9:52 PM

I'm looking for a way to write an efficient method that will return the sum of all the divisors of a number. For example, sigma(12) = 1 + 2 + 3 + 4 + 6 = 16.

So far all I can come up with is testing whether the number is divisble by each number from 2 to N/2. However, takes way too long on extremely large numbers. Can anyone help me out with a more efficient method? Thanks.

Jimbo · Apr 27th, 2006, 10:45 PM

well, up to N/2 would be a little extreme, since 2 would yield whether that is a divisor. You'd only have to to up to sqrt(N), as anything less would get you the pair of divisors.

OpenLoop · Apr 27th, 2006, 11:10 PM

Quote:

Originally Posted by Jimbo

well, up to N/2 would be a little extreme, since 2 would yield whether that is a divisor. You'd only have to to up to sqrt(N), as anything less would get you the pair of divisors.

that would give you the prime divisors. Then you can multiply the existing divisors to get the rest of the group. However, i don't think it is efficient...

titaniumdecoy · Apr 28th, 2006, 1:27 AM

That seems too complicated. Isn't there an easier (and faster) way?

Jimbo · Apr 28th, 2006, 2:32 AM

What I meant was, if you divide by 2 and it is a divisor, then N/2 is also one. so there's no reason to go up past sqrt(N), as any divisor > sqrt(N) will have a corresponding divisor < sqrt(N)

:banana:

OpenLoop · Apr 28th, 2006, 9:12 AM

but he wants all the devisors...
I don't think there is any easier way. I don't recall any theore for divisors calculation (except for the ones mentionned here already).

DaWei · Apr 28th, 2006, 9:54 AM

I don't think Jimbo is suggesting that sqrt (N) is the answer; I think he's suggesting that it is a reasonable limit....

bl00dninja · May 8th, 2006, 2:43 AM

well every number is divisble by 1 and itself...then you may have unique divisors like 2, 3, 5, and seven. at some point you're going to have to set a limit for the numbers. 1000000 is divisible by 2 and 4 and others...and ten times that is divisible by those and others plus all of those plus ten times that and on and on...maybe you want to just develop an algorithm for finding primes up to that number and multiples of those up to that number and trying those on a case-by-case basis. i'm drunk right now, but this still seems weird...

stack overflow ring a bell?

Ooble · May 8th, 2006, 10:00 AM

The guys are right. I wrote a couple of little Python scripts to find out exactly how much faster just counting up to the square root was, and it's rediculous. When finding the factors of, say, one billion (1,000,000,000), the faster script took half a second; the slower is still going, and I started it two minutes ago.

OpenLoop · May 8th, 2006, 11:28 AM

Quote:

Originally Posted by Ooble

The guys are right. I wrote a couple of little Python scripts to find out exactly how much faster just counting up to the square root was, and it's rediculous. When finding the factors of, say, one billion (1,000,000,000), the faster script took half a second; the slower is still going, and I started it two minutes ago.

That's partly due to the scientific fact that Python SUCKS :p

Apr 27th, 2006, 9:52 PM	#1
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 931 Rep Power: 4	Sum of Divisors I'm looking for a way to write an efficient method that will return the sum of all the divisors of a number. For example, sigma(12) = 1 + 2 + 3 + 4 + 6 = 16. So far all I can come up with is testing whether the number is divisble by each number from 2 to N/2. However, takes way too long on extremely large numbers. Can anyone help me out with a more efficient method? Thanks.

Apr 28th, 2006, 9:54 AM	#7
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	I don't think Jimbo is suggesting that sqrt (N) is the answer; I think he's suggesting that it is a reasonable limit.... __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

May 8th, 2006, 2:43 AM	#8
bl00dninja Programming Guru Join Date: Oct 2004 Location: namespace std Posts: 1,246 Rep Power: 6	well every number is divisble by 1 and itself...then you may have unique divisors like 2, 3, 5, and seven. at some point you're going to have to set a limit for the numbers. 1000000 is divisible by 2 and 4 and others...and ten times that is divisible by those and others plus all of those plus ten times that and on and on...maybe you want to just develop an algorithm for finding primes up to that number and multiples of those up to that number and trying those on a case-by-case basis. i'm drunk right now, but this still seems weird... stack overflow ring a bell? __________________ i put on my robe and wizard hat... Have you ever heard of Plato, Aristotle, Socrates?...Morons.

May 8th, 2006, 10:00 AM	#9
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	The guys are right. I wrote a couple of little Python scripts to find out exactly how much faster just counting up to the square root was, and it's rediculous. When finding the factors of, say, one billion (1,000,000,000), the faster script took half a second; the slower is still going, and I started it two minutes ago. __________________ Me :: You :: Them

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Apr 27th, 2006, 10:45 PM	#2
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 770 Rep Power: 3	well, up to N/2 would be a little extreme, since 2 would yield whether that is a divisor. You'd only have to to up to sqrt(N), as anything less would get you the pair of divisors.

Apr 28th, 2006, 1:27 AM	#4
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 931 Rep Power: 4	That seems too complicated. Isn't there an easier (and faster) way?

Apr 28th, 2006, 2:32 AM	#5
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 770 Rep Power: 3	What I meant was, if you divide by 2 and it is a divisor, then N/2 is also one. so there's no reason to go up past sqrt(N), as any divisor > sqrt(N) will have a corresponding divisor < sqrt(N) :banana:

Apr 28th, 2006, 9:12 AM	#6
OpenLoop Expert Programmer Join Date: May 2005 Location: East Lansing, MI Posts: 663 Rep Power: 4	but he wants all the devisors... I don't think there is any easier way. I don't recall any theore for divisors calculation (except for the ones mentionned here already).

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Software Design and Algorithms

Sum of Divisors