Programming Forums - Finding divisors

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - Finding divisors (http://www.programmingforums.org/showthread.php?t=12318)

Finding divisors

Hi, I'm new here and I'm also kind of new to C++. For one of my exercises I'm required to find the number between 1 - 1000 with the most divisors. To start, I am trying to find the divisors of 1000. Here is the program I have:

#include <iostream.h>



main()

{

      int x;

      int y;

      float remainder;

      int quotient;

      

      remainder = x % y;

      quotient = x / y;

      

      if (x == 1000)

      {

          for (y = x; y >= 1; y--)

          {

              if (remainder == 0)

              {

                    cout << quotient << endl;

              }

          }

      }

      return 0;

}

So far it doesn't work. Is there any ways of improving it to get my results?

A couple of things spring to mind immediately.

First, in both C and C++, a variable is simply a way of accessing a memory location. Unless you put a meaningful value into this memory location, you cannot use it in a sensible manner, and you're trying to compute the remainder and quotient of the (unknown) values of an uninitialized x and y. Even if the compiler automatically did set these to a default value, that would be zero, and then your code would crash (since dividing by zero is an error). The moral of the story: always explicitly initialize variables before using them, or trouble will follow.

The second thing is that, even if x and y were properly inititialized, they are initialized outside the loop. That means that their values will not change, and each iteration of the loop will behave the same. What you want is to initialize the values at the start of the loop, each and every iteration. You will probably also need to use nested loops. The outer loop will initialize the number for which you are trying to find divisors, and the inner loop will loop through, checking all divisors for that number (hint: you only need to check divisors less than or equal to half the number's value). Also, you're not actually counting the divisors. What you need is another variable (initialized at the start of the outer loop to zero) that holds this value. Then, each time in the inner loop where you find number % divisor equals zero, you know it is a factor of the number.

If you've been taught about writing functions (besides main(), I mean), then you could implement this as a function call. It might help make the code easier to understand with a function like countDivisors(int number).

Lastly, while you might be really new to the code, at least your post asked the question in a good way, and thanks for that. Read the stickies, write an intro post, and welcome to the forum. :)

I suggest you take your code and go over it. Write exacly what it does on a piece of paper.;) Stuff outside the braces of the loop doesen't get repeated.

Thanks guys, you all really helped!

I'll post my new results once I can figure it out.

Okay, here is my program for finding the divisors of 50

#include <iostream.h>



int i = 50;

int divisor;

int total;



main()

{    

     for (divisor = 1; divisor <= i / 2; divisor++)

     {

         if ((i % divisor == 0) && (i != divisor))

         {

            total = total + 1; 

         }

     }    

     cout << "The total number of divisors of 50 are " << total << endl;

     return 0;

}

I think I'm on to a good start. How would I integrate this into a program that finds the integer from 1 to 1000 with the most divisors?

A few comments;

1) Move your variable declarations (i, divisor, total) into the main() function. You have made them global/static variables which is not really neccessary, and often undesirable in practice. A side-effect of this is (often) that the value of total printed out will be garbage. That side-effect can be fixed by initialising total (setting it to a value) before entering the loop. [The reason for the side-effect is that static variables are initialised to zero, but non-static variables are not guaranteed to be initialised to anything].

2) Explicitly declare main() as;

int main()

Without this your code is not valid C++. The technique of leaving off the return type, and it defaulting to int, is a very old feature of C (and which is deprecated i.e. scheduled for removal from C)

3) You might want to consider the fact that 1 is always a divisor of any integer, so you don't need to explicitly check it in your loop.

4) "i" is not a particularly descriptive variable name in this case.

5) <iostream.h> is non-standard. Use <iostream> instead. If your compiler complains about that (eg not being able to find a header named iostream), it is antique and you should seek a newer compiler -- there are better ones freely available. A side effect of that is that your line using cout will trigger errors: either change it to;

std::cout << "The total number of divisors of 50 are " << total << std::endl;

or put a

using namespace std;

somewhere between including <iostream> and the first function in your file. I prefer the first option, and almost never employ a "using" directive; textbooks and uninformed beginners will often tell you to prefer the second.

EDIT: I was going to talk about making your thing into a function, but Jessehk has done that.

EDIT: grumpy caught all the little details. :)

You're on the right track. :)

Just wrap what you have there into a function.

int divisor_count( int n ) {
        int count = 1;
 
        // For every number upto n...
        for ( int i = 2; i <= n; i++ )
                // Check if n is divisible...
                if ( n % i == 0 )
                        ++count;
 
        return count;
}

That function will return the total number of divisors for a single integer n.

Now, all you have to do is call that function for every number in the range, and keep track of the number which gives you the largest number of divisors.

Okay, how will I be able to keep track of the number with the most divisors? Sorry if that was a newbie question.

Here's some pseudo-code:

max_divs  = 0

max_numb = 0



for x from 1 to 1000

    divs = get divisors for x 

    if divs is greater then max_divs then

        set max_numb to x

        set max_divs to divs

    end if

end for



display max_numb

Now translate that into C++.

Okay this is as far as I've gotten:

#include <iostream.h>



int divisor_count (int n);



int main()

{    

     int x;

     int divisors;

     int max_divs = 0;

     int max_num = 0;

     int last_num = 1000;



      for (x = 1; x <= last_num; x++)

      { 

          divisors = divisor_count(int x);

          if (divisors > max_divs)

          {

             max_num = x;

          }

      }

      cout << "The number with the most divisors is " << max_num << endl;

      return 0;

} 



int divisor_count (int n)

{

    int count = 1;



    for ( int i = 2; i <= n; i++ )

    {

        if ( n % i == 0 )

            ++count;

    }

    return count;

}

But I'm getting a "expected primary-expression before "int" error. Could anyone tell me why this is happening?