prime numbers code error..

amahja56 · #1 (**permalink**) January 14th, 2005, 01:48 PM

hi people,
i was trying to have fun with some c++ codes....it seems easy but ..i really got stuck because i ididnt get the logic of the primary number..or in better way....how to convert that logic in logical statement.!

here is the code

# include <iostream.h>
# include <conio.h>
# include <iomanip.h>

bool prime(int n);

int main()
{

    int count = 0;

    cout<<"the prime numbers from 1 to 10000 are :\n";

            for(int loop=2; loop<=10000; ++loop)
                if(*********) //make call to prime()
                {
                     ++count;
                     cout<<setw(6)<<loop;

                     if(count%10==0)
                         cout<<'\n';
                } // end if

                cout<<"\nthere were :"<<""<<count<<" "<<"prime numbers";
                return 0;

}

bool prime(int n)
{
    for(int i=2; i<=10000 ; i++)
        if(//test if n is divisible by i//)
            return false;

        else
            return true;
}

to test if n is divisible by n:

i have tried the following:
if(n%i!=0)
return fale
else return true;

i also have tried many logical statements but none of them work properly...so..i think i missing the logic of this..can anyone help me please?

thank you

mehdi62b · #2 (**permalink**) January 19th, 2005, 01:33 PM

for prime numbers there are two general ways,
n is a prime number if it has just two factors.(1 and that number)
for example,
2 is a prime number because its factors are{1,2}
3 is a prime number because its factors are{1,3}
23 is a prime number because its factors are{1,23}
6 is not a prime number because its factors are{1,2,3,6}
1 is not a prime number because its factor is{1}
every even number except 2 is not a prime number because its factors are more than 2(for example for 2n we have at least 1,2,n,2n as its factors}
and its code is,

Code:

//Not tested
bool IsPrime(int n)
{
  int counter=0;
  for(int i=1; i<=n ; i++)
   if (n%i==0) counter++;
  if (counter==2) return true;
  return fasle;
}

but another way is,
for every number like n,it is a prime number if there is no factor from 2 to its root(n^1/2) for example,
12 is not a prime because between ranges from 2 to 3(3<=12^1/2) 2 and 3 are the factors for 12,
and its code is,

Code:

//Not tested
bool IsPrime(int n)
{
  //I'm not sure what is the right function for sqrt
  int root=(int)sqrt(n);
  for(int i=2; i<=root ; i++)
   if (n%i==0) return fasle;
  return true;
}

probably the second way is faster and better,
(if you just want to generate the prime numbers between two number there is a smart solution called Eratostenes Sieve,check out its link).

_____________________________
Mehdi.
software engineering student.
Looking for a good job for summer 2005.