Expert: Ralph McArdell - 8/31/2009

Question
hi

my programme is suppost to print in the screen all the prime numbers smaller than the one i enter in the command line. but there are numbers missing or appering wrong ( if I enter 11 are appearing 5, 7 and 9 when should be 2, 3, 5, 7, 11).

Note:a prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.To check whether a given number is prime, rather than generate a list of primes given a number n, one divides n by all numbers m less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime.



#include <iostream>
#include<cmath>

using namespace std;

bool primo (int n);

int main(int argc, char* argv[])
{
int m, aux,duv;
if (argc<2)
cout<< "Write a number in the command line" << endl;
else
{
m=atoi(argv[1]);

for(aux=1; aux <m; aux++)
{
duv=primo(aux);
if (duv == 1)
cout << aux<< endl;

}
}
}

bool primo (int n)
{
int i,duvida;

if (n ==1)
return 0;
else
{
if(sqrt(n)== 1)
duvida=1;
for (i=2; i< sqrt(n); i++)
{
if(n%i == 1)
duvida= 1;
else{
duvida= 0;
break;}
}
return duvida;
}
}  

Answer
Well, because you have made a mistake some where - errm , obviously!

The task then is to find what the problem is - or what the problems are.

Your primary (no pun intended) candidate for problems is the primo function. You can find out what is wrong by plugging in values and see what happens - doing this by following the code manually (or mindually maybe as its your brain not your hands that is used). If you have one to hand and know how to use it you can of course use a debugger to break into and step through the code examining the values of the variables and the code paths taken.

However before we get into plugging in values, a few things I noticed about your code.

First, as you know 1 is not prime why are you even considering it in the for(aux loop in main?

Why do you explicitly check in primo for 1:

   if (n ==1)
   return 0;

and then  check again effectively:

if n not 1 (i.e. in the else clause).

   if(sqrt(n)== 1)
   duvida=1;
   
as if n were greater than 1 then sqrt(n) would not be equal to 1 (sqrt works with floating point values).

I notice that you perform no error checking on the number supplied. What about values supplied such as: 0, -1, -2, -123, notANumber?

Remember that you cannot tell from atoi if the value entered were 0 or not a number - it returns 0 in both cases.

I do not know if you did indent your code by I received it all up against the left hand side, with some statements etc. started on the same line and others not etc.. If you did nicely format your code then please ignore this. If not then please, please, please indent your code - it makes understanding what is going on much easier, so rather than this:

   #include <iostream>
   #include<cmath>

   using namespace std;

   bool primo (int n);

   int main(int argc, char* argv[])
   {
   int m, aux,duv;
   if (argc<2)
   cout<< "Write a number in the command line" << endl; else { m=atoi(argv[1]);

   for(aux=1; aux <m; aux++)
   {
   duv=primo(aux);
   if (duv == 1)
   cout << aux<< endl;

   }
   }
   }

   bool primo (int n)
   {
   int i,duvida;

   if (n ==1)
   return 0;
   else
   {
   if(sqrt(n)== 1)
   duvida=1;
   for (i=2; i< sqrt(n); i++)
   {
   if(n%i == 1)
   duvida= 1;
   else{
   duvida= 0;
   break;}
   }
   return duvida;
   }
   }

I think you will agree that the following is easier to see which parts code are grouped with and within which other parts of the code:

   #include <iostream>
   #include<cmath>

   using namespace std;

   bool primo (int n);

   int main(int argc, char* argv[])
   {
       int m, aux,duv;
       if (argc<2)
           cout<< "Write a number in the command line" << endl;
       else
       {
           m=atoi(argv[1]);

           for(aux=1; aux <m; aux++)
           {
               duv=primo(aux);
               if (duv == 1)
                   cout << aux<< endl;
           }
       }
   }

   bool primo (int n)
   {
       int i,duvida;

       if (n ==1)
           return 0;
       else
       {
           if(sqrt(n)== 1) // remove - it is redundant as you just checked for n==1 above
               duvida=1;  //  and n>1 gives sqrt>1
           for (i=2; i< sqrt(n); i++)
           {
               if(n%i == 1)
                   duvida= 1;
               else
               {
                   duvida= 0;
                   break;
               }
           }
           return duvida;
       }
   }

It also seems you are using a predominately C style with a thin veneer of C++. For example, in primo you do not need i and duvida if n == 1, so why not define them only when required, and use the correct types for your variables? You are returning a bool so why is duvida an int? Why not use a bool and true/false rather than an int and 1/0 (and not use this value directly in main)?

   bool primo (int n)
   {
       if (n ==1)
           return false;
       else
       {
           bool duvida(false);
           if(sqrt(n)== 1)
               duvida=true;
           for (int i=2; i< sqrt(n); i++)
           {
               if(n%i == 1)
                   duvida= true;
               else
               {
                   duvida=false;
                   break;
               }
           }
           return duvida;
       }
   }

Which can be reduced further, as you are using Boolean expressions in the if statements to set duvida anyway why not use them to set duvida directly?

   bool primo (int n)
   {
       bool duvida(! n==1);
           
       if ( duvida )
       {
           for (int i=2; i< sqrt(n); i++)
           {
               duvida = (n%i == 1);
               if ( ! duvida )
               {
                   break;
               }
           }
           
       }

       return duvida;
   }

In fact we can move the break if duvida false into the for loop test:

   bool primo (int n)
   {
       bool duvida(! n==1);
           
       if ( duvida )
       {
           for (int i=2; duvida && (i< sqrt(n)); i++)
           {
               duvida = (n%i == 1);
           }
           
       }

       return duvida;
   }

The loop now continues while both duvida is true and i< sqrt(n), which makes the surrounding if test redundant:

   bool primo (int n)
   {
       bool duvida(! n==1);
           
       for (int i=2; duvida && (i< sqrt(n)); i++)
       {
           duvida = (n%i == 1);
       }
           
       return duvida;
   }

OK that is clearer and I can see one mistake I think. But let us plug in some values and see what happens.

First a simple one. n = 1

n==1 is true so ! n==1 is false so duvida is initialised to false.

This makes the test in the for loop:

   false && (don't care) == false

so the loop is skipped and false is returned.

Now another simple one. n = 2.

n==1 is false so ! n==1 is true so duvida is initialised to true.
This makes the for loop condition:

   true && 2 < sqrt(2) == true && false == false

So the loop is skipped and true returned.

Now let's try n=3:

Again duvida is initialised to true which makes the for loop condition:

   true && 2 < sqrt(3) == true && false == false

So the loop is skipped and true returned.

Now let us try n=4, the 1st non-prime or identity value

Again duvida is initialised to true which makes the for loop condition:

   true && 2 < sqrt(4) == true && false == false

sqrt(4) is 2, although because we get a floating point value back from sqrt this value may be fractionally more (OK) or less (oops) than 2. If it is less then the implementation of the logic is incorrect.

So the loop is skipped and true returned. Oops.

So we have uncovered two problems: the first in the logic itself - you should use <= in the test not < for this case. The other is due to the imprecise nature of floating point arithmetic. In this case we can fix it by adding say 0.5 to the result of the sqrt call and cast the value back to an integer. This would make the for loop statement:

       for (int i=2; duvida && (i<=static_cast<int>(sqrt(n)+0.5)); i++)

Now if we re-run the n=4 case:

Again duvida is initialised to true which makes the for loop condition:

   true && 2<=static_cast<int>(sqrt(4)+0.5)) == true && 2<=static_cast<int>(2.5))
       == true && 2<=2 == true && true

We enter the loop.

   duvida = (4%2 == 1) == (0 == 1) == false

duvida is false, we terminate the loop:

       false && (don't care) == false

and return false.

In fact adding 0.5 to the result returned from sqrt before casting to an int will round up to the next integer so the test for 3 changes and we enter the loop for 3 as well - which is probably 'more correct'. In this case 3%2 == 1 so we still get a true return.

This will fix your code for _small_ values only. To see this let us try entering n=11 (i.e. the user entered 12 or more)

Here we start as per all non n=1 cases and duvida is initialised to true which makes the for loop condition:

   true && 2<=static_cast<int>(sqrt(11)+0.5)) == true && 2<=static_cast<int>(3.8165))
       == true && 2<=3 == true && true

We enter the loop.

   duvida = (11%2 == 1) == (1 == 1) == true

but in this case:

   i=3

and we still have:
   
   true && 3<=3 == true && true == true

So we go around the loop again:

   duvida = (11%3 == 1) == (2 == 1) == false

The loop terminates and false is returned.

Thus the code incorrectly states that 11 is not prime.

This is because a prime number is a number that can only be divided wholly by 1 and itself. Hence dividing by all other values leaves a remainder - this you have grasped. Your mistake is not realising that a remainder can be _more_ than 1, as in this case. Hence n%i == 1 is only true for some cases and not all cases which may indicate a prime. In this case specifically 11 / 3 leaves a remainder of 2. Likewise 37 % 5 gives a remainder of 2 and 139 % 11 gives 7. The general test is that if the remainder is zero then the number is not prime as it divides exactly, or it is still possibly prime if the remainder is not zero:

   duvida = !(n%i == 0);

These changes should fix the primo function. You should still add error checking for the value entered by the user and you should probably check into the floating point rounding issue - can you reduce the value added on below 0.5 (maybe to 0.1 or 0.0001) and still get correct results? Would it be better to calculate this value _once_ rather than every time around the loop (floating point operations can potentially be expensive)?

Here is a test program I used to check out the logic of primo:

   #include <iostream> // for std::cout
   #include <iomanip>  // for std::boolalpha
   #include <ostream>  // for std::ostream
   #include <cmath>    // for sqrt
   #include <cstdlib>  // for atoi

   bool primo (int n)
   {
       bool duvida(! (n==1));
           
       for (int i=2; duvida && (i<=static_cast<int>(sqrt(static_cast<double>(n))+0.5)); i++)
       {
           duvida = !(n%i == 0);
       }
           
       return duvida;
   }

   void Print( int n, std::ostream & out=std::cout )
   {
     out << n << " is prime is "  << std::boolalpha << primo(n) << std::endl;
   }

   int main()
   {
       for ( int i=1; i<102; ++i )
       {
           Print(i);
       }
   }

Note that my standard library implementation has the C++ specific overloads for sqrt for float, double and long double and so I have to explicitly pick one (the static_cast<double>) for the integer n value to be converted to as the compiler could not decide between them (doh!).

Hope this helps and please do _not_ expect me to go into this level of detail for what is essentially stuff you should have done. I did it this time to show you how to go about it. Next time I would expect you to have tried test procedures yourself.

Oh you might like to look at ways to determine if an integer is prime or not. Here are some Wikipedia articles for starters:

   http://en.wikipedia.org/wiki/Prime_number (specifically the section 'Verifying primality')
   http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
   http://en.wikipedia.org/wiki/Primality_test

Have fun and good luck with you programming.