prime number problem

[gong]

hi
can someone help me?

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
{

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

[jsmith]

if( n % i == 1 )

==> so if the remainder of dividing n by i is exactly 1, the number is prime???

Other notes:

if( sqrt(n) == 1 )
duvida = 1;

is irrelevant, since the for loop will always set duvida anyway.

Secondly, if the function returns bool, you should return true and false instead of 1 and 0
as a matter of style.

[gong]

exactly ! if the remainder of dividing n by i is exactly 1, the number is prime.


but do you know what is wrong with the code?

thanks

[chrisname]

What? Not necessarily. 7 % 5 != 1. Its equal to not 0, so true. If it is divisible then it will leave 0, thus the number is not prime.

[jsmith]

An integer n, n > 2, is prime iff for all integers i, 1 < i < n, n % i != 0.

[buffbill]

Something like this may serve;

 bool  isPrime = true;            //declare isPrime and initialise to true
            for(int i=0;i<=num;i++)//cycle through each number
               {                               //between 0 and num        
                  for(int j=2;j<=num;j++)
                     {
                         if(i!=j && i%j==0 || i==1)
                            {
                                isPrime = false;
                                break;
                            }
                    }
                    if(isPrime){cout<<"Prime: "<<i<<" ";
                    }
                    isPrime=true;
              }