11
\$\begingroup\$

My program is complete and working, but I would like second opinions on it. The program prompts the user for a positive value that will serve as the maximum for the range that will be checked for perfect numbers. Although this is one of those do-what-you-want-with-it problems, I have to keep the two prototypes. Are there any extra adjustments I should make in the program or is it already efficient the way it is?

#include "stdafx.h"
#include <iostream> 
using namespace std; 

/* Function prototypes */
bool isPerfect(int n); 
int sumOfProperDivisors(int n); 

/* Main program*/
int main()
{
    // Declare variable(s)
    int bound;  // Stores upper limit of number range

    // Prompt user to enter a positive integer
    cout << "Enter upper bound: "; 
    cin >> bound; 

    // Display the information 
    cout << "\n\nThe perfect numbers between 1 and " << bound << " are: " << endl; 

    for (int i = 1; i <= bound; i++)
    {
        if (isPerfect(i))
        {
            cout << i << endl; 
        }
    }

    system("PAUSE"); 

    return 0; 
}

/*
* Function: isPerfect
* -------------------
* Returns the sum of the number(s) within the testing range  
*/
bool isPerfect(int n)
{
    int sum = 0; 

    for (int i = 1; i < n; i++)
    {
        if (n % i == 0)
        {
            sum += i; 
        }
    }

    return sum == n; 
}

/*
* Function: int sumOfProperDivisors
* ---------------------------------
* Returns the sum of a number's divisors 
*/
int sumOfProperDivisors(int n)
{
    int sum = 1; 

    for (int i = 2; i <= n/2; i++)
    {
        if ((n % i) == 0)
        {
            sum += i; 

            if (i * i == n) 
            {
                sum -= i; 
            }
        }
    }

    return sum; 
}
\$\endgroup\$
18
\$\begingroup\$

MS Specific

MS specific don't need it here

#include "stdafx.h"

Namespace std

Never do this.

using namespace std; 

I know every book you read does this. This is because they are paying for the ink. Its actually very bad style and will cause a huge amount of problems for any program longer than ten lines or for code that lives longer than a year. So it is bad habit you should get out of the habit of doing.

The reason they picked std rather than standard so it is easy to type and use as a prefix. Its not that much harder to type than the normal object or type.

std::cout << "Testing\n"; // Not that hard see.

For details about the problem see: Why is “using namespace std;” considered bad practice?

Comments

Don't add us-less comments.

/* Main program*/
int main()
{
    // Declare variable(s)

Comments can do more harm than good when used incorrectly. This is because over time comments fall out of line with the code unless very explicitly maintained. Because the compiler does not check the comments for accuracy this happens a lot.

Thus a maintainer who sees a comment that does not agree with the code then has to try and work out which is wrong. The code or the comment and then has to fix it.

You should restrict your comments to "WHY" comments. Why is the code working like this. "WHY" we need to do something. The code itself should explain "HOW" (as long as you use good variable and function names).

See: What are examples of comments that tell you why instead of how or what?

USless comment: (I can see what it does by reading the code)

    // Display the information 
    cout << "\n\nThe perfect numbers between 1 and " << bound << " are: " << endl; 

Don't like this comment.

/*
* Function: isPerfect
* -------------------
* Returns the sum of the number(s) within the testing range  
*/

In this case the comment says one thing. The name of the function says something else. It does not return the sum it returns bool. Because the function is named perfectly you don't really need to say anything (the function name is enough).

bool isPerfect(int n)

Don't particularly like the comment.

/*
* Function: int sumOfProperDivisors
* ---------------------------------
* Returns the sum of a number's divisors 
*/

It does not tell me anything that the name of the function already tells me.

Validate User Input

You don't validate user input.

    cin >> bound; 

Input from many sources can be trusted. Input from a human can not. Validate their input and anticipate that they will either be stupid or malicious in trying to crash your program.

std::endl and flushing

Prefer to use "\n" instead of std::endl.

     cout << "\n\nThe perfect numbers between 1 and " << bound << " are: " << endl; 

The reason is that std::endl just puts "\n" then flushes the stream. Stream flushing can make the code very inefficient if done incorrectly. Also the streams flush themselves when they need to without your help.

see: C++: “std::endl” vs “\n”

Prefer Prefix increment

Prefer prefix increment ++i over suffix increment i++.

    for (int i = 1; i <= bound; i++)

Though in this case it does not explicitly matter. If sombody came along and changed the type of you loop (to say BigInt a type that supports 128 bit integers) then it may make a difference. Also you want them to be able to change the type without having to change any code and still get the best performance.

The reason that i++ can be less efficient for types is because of the default way of implementing the operator.

see: Questions about operator overloading

The default method means that the suffix version creates an extra copy of the object that is not required by the prefix version.

System Pause Bad

Don't do this.

    system("PAUSE"); 

Use a standard happy way of apuing the the code.

cin.ignore(255, '\n'); // ingore input to the end of line (as you did not do that in the previous read).
std::cout << "Hit Enter to continue\n";
cin.get();             // Wait for user input to be flushed.

Return in Main

The function main() is special. If you don't specify a return value the compiler will generate one for you return 0. It is the only function this will happen in.

As a result we use having no return as an indicator to the maintainer that there is no way for this application to fail. If you have an explicit return 0; at the end then I am looking through your code to find a place where you return an error code.

    return 0; 
\$\endgroup\$
10
\$\begingroup\$

This will be a list of things I noticed without looking at the bigger picture.

Includes and namespaces

You include stdafx.h, which is a precompiled header. In your case, there is no point in keeping it around and probably included by default by your compiler. It does have a good reason to exist, but not in projects this small.

using namespace std; is considered bad practice. Short code is not a requirement in C++, clear code is preferred.

Declarations

Your 'prototypes' are actually declarations. They are there to tell the compiler the functions exist and should look elsewhere to find the definition. Those can be removed entirely by placing the definitions above main. Whether or not this is preferred is mostly a matter of style, preference and the architecture of the project.

System

system("PAUSE"); is considered bad practice. cin.get() halts the program waiting for user input in a more standardized and portable-friendly way.

Return

return 0; is a legacy from C. In C++, it's no longer required to write this manually. The compiler will take care of returning 'normal' if no errors where thrown or other returns (like -1) are encountered.

Input validation

You expect the user to input a positive number at cin >> bound;. However, there is nothing in your program checking whether the input really is positive. Now, a negative number will just skip the loop and end without doing anything excepting printing the input. But have you checked what happens when you input a non-numeric character like z?

You'll either want to validate or sanitize your input data (or both).

\$\endgroup\$
8
\$\begingroup\$

Both the methods you wrote for summing divisors are unnecessarily inefficient.

Divisors come in pairs. If you know one divisor of a pair, it's trivial to find the other divisor of that pair. In a pair of divisors, one divisor is less than or equal to the square root, and the other is greater than or equal to the square root.

You can find all the divisors of a number by searching only up to the number's square root.

\$\endgroup\$
6
\$\begingroup\$

Code reuse

You are doing the same thing twice, I suggest:

bool isPerfect(int n) {
     return n == sumOfProperDivisors(n);
}

Also, the second method has better time complexity, so the code is now faster.


A ternary instead of if may make the loop in isPerfect faster but I made no benchmark and may be considered premature optimization.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you, Caridoc! Your comment was very helpful since I was trying place a function call for the sum function somewhere. \$\endgroup\$ – Duck Aug 22 '15 at 21:56
3
\$\begingroup\$

Rather than pausing, like you did here:

system("PAUSE");

I would just do something like this (Thanks @Loki for the tip!):

std::cin.getc()

This way the user can look at the output all they want, and then exit by pressing ENTER.

In addition, it's a horrible idea to have using namespace std; in your code. See this Stackoverflow question for more details.

\$\endgroup\$
2
\$\begingroup\$

Specifically with regards to efficiency, and without really working too hard on understanding factorisation techniques, it is simple enough to get a huge performance gain by noting that factors come in pairs.

This means that when we find a factor we also add its cofactor and therefore only need to search for factors less than or equal to sqrt(n).

Note how that limit is computed before the loop, not on each iteration thereof.

bool isPerfect(int n)
{
    int sum = 1;
    int maxFactor = static_cast<int>(sqrt(n)); // Need <math.h>
    for (int i = 2; i <= maxFactor; ++i)
    {
        if (n % i == 0)
        {
            sum += i;
            int cofactor = n / i;
            if (cofactor != i)
                sum += cofactor;
        }
    }
    return sum == n;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.