Programming Forums > Application Development > C++

gamerfelipe · Jan 6th, 2007, 6:26 PM

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:

(Toggle Plain Text)

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

lectricpharaoh · Jan 6th, 2007, 6:58 PM

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.

Wizard1988 · Jan 6th, 2007, 6:58 PM

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.

gamerfelipe · Jan 6th, 2007, 7:20 PM

Thanks guys, you all really helped!

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

gamerfelipe · Jan 6th, 2007, 7:36 PM

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

(Toggle Plain Text)

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

grumpy · Jan 6th, 2007, 7:58 PM

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;

(Toggle Plain Text)

    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;

(Toggle Plain Text)

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

or put a

(Toggle Plain Text)

   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.

Jessehk · Jan 6th, 2007, 7:58 PM

EDIT: grumpy caught all the little details.

You're on the right track.

Just wrap what you have there into a function.

 cpp Syntax (Toggle Plain Text) 
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;
}
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.

gamerfelipe · Jan 6th, 2007, 8:07 PM

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

Jessehk · Jan 6th, 2007, 8:17 PM

Here's some pseudo-code:

(Toggle Plain Text)

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

gamerfelipe · Jan 6th, 2007, 8:39 PM

Okay this is as far as I've gotten:

(Toggle Plain Text)

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

Jan 6th, 2007, 6:26 PM	#1
gamerfelipe Newbie Join Date: Jan 2007 Location: Hershey, the sweetest place on earth Posts: 19 Rep Power: 0	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: (Toggle Plain Text) #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; } #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?

Jan 6th, 2007, 6:58 PM	#2
lectricpharaoh Caffeinated Neural Net Join Date: Jun 2005 Location: Wet west coast of Canada Posts: 1,126 Rep Power: 5	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. __________________ And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot. - Vaarsuvius, Order of the Stick

Jan 6th, 2007, 6:58 PM	#3
Wizard1988 Professional Programmer Join Date: Oct 2005 Location: Chitown Posts: 422 Rep Power: 4	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. __________________

Jan 6th, 2007, 7:36 PM	#5
gamerfelipe Newbie Join Date: Jan 2007 Location: Hershey, the sweetest place on earth Posts: 19 Rep Power: 0	Okay, here is my program for finding the divisors of 50 (Toggle Plain Text) #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; } #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? Last edited by gamerfelipe; Jan 6th, 2007 at 7:46 PM.

Jan 6th, 2007, 7:58 PM	#6
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,254 Rep Power: 5	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; (Toggle Plain Text) int main() 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; (Toggle Plain Text) std::cout << "The total number of divisors of 50 are " << total << std::endl; std::cout << "The total number of divisors of 50 are " << total << std::endl; or put a (Toggle Plain Text) using namespace std; 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.

Jan 6th, 2007, 7:20 PM	#4
gamerfelipe Newbie Join Date: Jan 2007 Location: Hershey, the sweetest place on earth Posts: 19 Rep Power: 0	Thanks guys, you all really helped! I'll post my new results once I can figure it out.

Jan 6th, 2007, 7:58 PM	#7
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 646 Rep Power: 4	EDIT: grumpy caught all the little details. You're on the right track. Just wrap what you have there into a function. cpp Syntax (Toggle Plain Text) 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; } 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. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Jan 6th, 2007, 8:07 PM	#8
gamerfelipe Newbie Join Date: Jan 2007 Location: Hershey, the sweetest place on earth Posts: 19 Rep Power: 0	Okay, how will I be able to keep track of the number with the most divisors? Sorry if that was a newbie question.

Jan 6th, 2007, 8:17 PM	#9
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 646 Rep Power: 4	Here's some pseudo-code: (Toggle Plain Text) 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 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++. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Jan 6th, 2007, 8:39 PM	#10
gamerfelipe Newbie Join Date: Jan 2007 Location: Hershey, the sweetest place on earth Posts: 19 Rep Power: 0	Okay this is as far as I've gotten: (Toggle Plain Text) #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; } #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?

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

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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Finding Random Min and Max	imagikricei	C++	18	Jun 12th, 2006 1:29 PM
Sum of Divisors	titaniumdecoy	Software Design and Algorithms	20	May 14th, 2006 4:24 PM
Finding Patterns	jobobshishkabob	C++	24	Feb 26th, 2006 3:49 AM
finding the number of spaces in a String	squishiful	Java	6	Jul 6th, 2005 6:43 PM
Help with finding windows programming books	some1	C++	11	Feb 9th, 2005 10:19 AM

Programming Forums > Application Development > C++

Finding divisors