Thread: Divisor Algorithm

  1. #1
    Registered User
    Join Date
    Oct 2008
    Location
    CA
    Posts
    19

    Divisor Algorithm

    I have written a workable divisor algorithm that does this:

    In order to get all divisors of a some number called "Num":

    You search in the the range (1, num/2 + 1) and then do a for loop:

    something like this:

    for (int i =0; i < num; i ++){
    if (num%i) == 0);
    //add to the list of divisors

    Someone else told me I need to make the range up to num/2 + 1 rather than num/2. Why the +1?

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    > Why the +1?
    Because integer division truncates.

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    For example, if num == 20, then 20/2 is 10, and if your loop specifies < 10, then you won't find 10 as a divisor for 20. Therefore, you add 1 to 10, and now you will find 10 as a divisor.
    Mainframe assembler programmer by trade. C coder when I can.

  4. #4
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    477
    You only need to loop up to sqrt(num). The other divisors can be found by then dividing num with the divisors you find within that range.

    Code:
    int i, count = 0;
    
    for( i = 0; i < sqrt(num); i++)
    {
         if(num % i == 0)
         {
              // Add i to list of divisors.
              // Add num / i to list of divisors.
              count ++;
         }
    }
    
    count *= 2;
    This code will give you all divisors as well as the count, with twice as little work.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  5. #5
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by IceDane View Post
    with twice as little work.
    as in half the work?

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  6. #6
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    477
    Quote Originally Posted by QuantumPete View Post
    as in half the work?

    QuantumPete
    Pedantic semantics, but should have known - board full of programmers. Haha.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Hmmmmmmmmmmm

    Fixed:
    Code:
    int i, count = 0, square;
    
    for( i = 0, square = sqrt(num); i < square; i++)
    {
         if(num &#37; i == 0)
         {
              // Add i to list of divisors.
              // Add num / i to list of divisors.
              count ++;
         }
    }
    count *= 2;

Popular pages Recent additions subscribe to a feed

Tags for this Thread