You are here:

# C++/Finding the primes

Question
This program is supposed to prompt the user for where they want their prime finding to start and just print out the primes it finds. It freezes up on me and I don't know why. Could you tell me why it doesn't seem to do the num2 loop?

#include <iostream>
#include <cmath>
using namespace std;

int main(void)
{
unsigned long long num1,num2,num3,num4;
cout << "What number do you want to begin with? ";
cin >> num1;
while(num1 > 18446744073709551615)
{
cout << "That number is too small, need a number less than 18446744073709551616 ";
cin >> num1;
}
for(num2 = num1; num2 <= 18446744073709551615; num2++)
{
for(num3 = 2; num3 <= num2; num3++)
{
do
{
num4 = num2%num3;
if(num3 == num2)
{
cout << num2 << " is a prime number!" << endl;
}
}while(num4 != 0);
}
}
return 0;
}

Your program has not locked up. It is running. Continuously.

In short:

num4 is dependent only on num2 and num3 values and these values are invariant during execution of the inner do..while loop.

What do I mean by that?

Well, you terminate the inner do..while loop dependent on the value of num4.

num4 is dependent only on the values of num2 and num3.

Neither num2 nor num3 vary with each iteration of the inner loop.

Hence this loop will either terminate after the first iteration or never.

Even if a few num2, num3 combinations allow the inner loop to terminate eventually a num2, num3 pair will yield a non-zero num4 value. In fact this is very likely, as many combinations of num2%num3 will yield a remainder.

I suggest you take on board a few things.

The first lesion to learn is that just because your program builds with no complaints from your compiler or linker does not mean that it is correct and bug free and will do what it is intended to do.

The second lesson is that usually it is _not_ the compiler and _not_ the library code that is in error. It is _your_ code. Always assume that it is your code (or maybe your build process) that is wrong to start with. If it is new code then it is untested and can therefore be assumed to be wrong until shown otherwise. If it is old code you have changed then these changes are new and are prime suspects for problems until proven otherwise (by testing and, if problems occur, by debugging).

The next lesson to learn is to actually read what you have written and _understand it_. How do you think I determined what you had done wrong?

If you cannot see what is going on straight off try running the program in your head (called a dry run). Using pencil or pen and paper to keep track of values (e.g. num2, num3, num4) helps.

By the way, just because I am a C++ expert does _not_ mean I can instantly understand any program I am presented with. On the other hand you should have a good idea of what your program should be doing.

You should also try asking questions of yourself like the one you asked me. You determined that the program had locked up and did not seem to be doing your outer loop. Well, having got that far you could look at your code and see what is between the start and end of the outer loop. It is a good bet that something has gone wrong here!

The next trick to seeing what is going wrong is to add additional trace output. For example in this case try something like:

for(num2 = num1; num2 <= 18446744073709551615; num2++)
{
cout << "Trace: num2=" << num2 << endl;

for(num3 = 2; num3 <= num2; num3++)
{
cout << "Trace: num3=" << num3 << endl;
do
{
num4 = num2%num3;

cout << "Trace: num4=" << num4 << endl;

if(num3 == num2)
{
cout << num2 << " is a prime number!" << endl;
}
}
while(num4 != 0);
}
}

Doing the above would focus you directly on what was going on. Note that I have left the trace output statements purposely not indented. This is to make them easy to spot and remove when not required anymore.

More permanent debugging code can be conditionally included using a specific macro, such as DEBUG:

#ifdef DEBUG
// debug only code
#endif

Or, the inverse, a macro that is defined to indicate non-debug builds, for example:

#ifndef NDEBUG
// debug only code
#endif

Some development environments use NDEBUG, such as projects defined by the Microsoft Visual C++ Visual Studio IDE (Integrated Development Environment). Others prefer the likes of DEBUG or variations.

Such techniques can be used to define debug output macros such as the Microsoft TRACE macros. These tend to expand to nothing for non-debug builds and to some sort of output statement for debug builds.

The final recommendation I am going to mention is to learn to use a debugger. Some are built into the development environment and very easy to use such as the debugger integrated into the MS Visual Studio IDE, Other are separate and not so easy to use such as the gdb debugger for the GNU tools. The first step is to ensure you build and link your program to include debugging information, the next is to run it under a debugger rather than directly. How you achieve these depends on what development tools you are using.

A debugger should allow you to break program execution, see what code was executed, look at values, set points in the code to break execution, step through the code one line at a time, resume execution, etc. Using these facilities on your program would soon reveal the problem. For example breaking execution at the outer for loop and single stepping though the program would show you that it gets stuck going round and round the inner loop. Alternatively breaking into program execution would also show that it was whizzing round the inner loop.

C++

Volunteer

#### Ralph McArdell

##### Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

##### Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials