I wim a beginer in C++ and i want to write a programme to display prime numbers .
say when i key in a number on the key board it should be able to tell me if it's a prime number

: I wim a beginer in C++ and i want to write a programme to display prime numbers .
: say when i key in a number on the key board it should be able to tell me if it's a prime number
:



int r=0;
cin<<NUM;
for(int i=2;i<=NUM;i++)
{
if(NUM%i==0)
{
r=1;
break;
}
}
if (r==0)
cout<<"The number is prime.";


this code will do the job.

:
: int r=0;
: cin<<NUM; //should be: cin>>NUM
: for(int i=2;i<=NUM;i++) //should be: for(int i=2;i<NUM;i++)
: {
: if(NUM%i==0)
: {
: r=1;
: break;
: }
: }
: if (r==0)
: cout<<"The number is prime.";
:
: this code will do the job.

It won't do the job due to two reasons I've marked in red.
A more complete, readable and complete example code can be found at

http://www.codepedia.com/1/CppPrime

See ya,

bilderbikkel

: :
: : int r=0;
: : cin<<NUM; //should be: cin>>NUM
: : for(int i=2;i<=NUM;i++) //should be: for(int i=2;i<NUM;i++)
: : {
: : if(NUM%i==0)
: : {
: : r=1;
: : break;
: : }
: : }
: : if (r==0)
: : cout<<"The number is prime.";
: :
: : this code will do the job.
:
: It won't do the job due to two reasons I've marked in red.
: A more complete, readable and complete example code can be found at
:
: http://www.codepedia.com/1/CppPrime
:
: See ya,
:
: bilderbikkel
:
:


Well... a prime number algo that doesn't check if a certain number is divisible by 2 is a bit embarrassing imo. Suggestion of how to optimize that code so that it only checks odd numbers:

bool isPrime(const int& x)
{
  if(x < 3)
    return true;
  else if(x % 2 == 0)
    return false;


  for (int i=3; i<x/2; i+=2)
  {
    if (x % i == 0) 
      return false;
  }

  return true;
}

This message was edited by Gregry2 at 2007-3-12 5:47:35

---

This message was edited by Gregry2 at 2007-3-12 5:44:11

---

: : :
: : : int r=0;
: : : cin<<NUM; //should be: cin>>NUM
: : : for(int i=2;i<=NUM;i++) //should be: for(int i=2;i<NUM;i++)
: : : {
: : : if(NUM%i==0)
: : : {
: : : r=1;
: : : break;
: : : }
: : : }
: : : if (r==0)
: : : cout<<"The number is prime.";
: : :
: : : this code will do the job.
: :
: : It won't do the job due to two reasons I've marked in red.
: : A more complete, readable and complete example code can be found at
: :
: : http://www.codepedia.com/1/CppPrime
: :
: : See ya,
: :
: : bilderbikkel
: :
: :
:
:
: Well... a prime number algo that doesn't check if a certain number is divisible by 2 is a bit embarrassing imo. Suggestion of how to optimize that code so that it only checks odd numbers:
:
:

: bool isPrime(const int& x)
: {
:   if(x < 3)
:     return true;
:   else if(x % 2 == 0)
:     return false;
: 
: 
:   for (int i=3; i<x/2; i+=2)
:   {
:     if (x % i == 0) 
:       return false;
:   }
: 
:   return true;
: }
: 

:

bool isPrime(const int& x)
{
  if(x == 2)
    return true;
  else if(x <= 1)
    return false;
  
  else if(x % 2 == 0)
    return false;


  for (int i=3; i<x/2; i+=2)
  {
    if (x % i == 0) 
      return false;
  }

  return true;
}

1 is not a prime number. Plus, prime numbers are natural numbers, thus not anything like 0, -1, -2, -3...

{2}rIng


EDIT: just corrections

:

: bool isPrime(const int& x)
: {
:   if(x == 2)
:     return true;
:   else if(x <= 1)
:     return false;
:   
:   else if(x % 2 == 0)
:     return false;
: 
: 
:   for (int i=3; i<x/2; i+=2)
:   {
:     if (x % i == 0) 
:       return false;
:   }
: 
:   return true;
: }
: 

:
: 1 is not a prime number. Plus, prime numbers are natural numbers, thus not anything like 0, -1, -2, -3...

Thanks for your correction. Indeed, negatives are not prime, but it depends on your definition if one is prime. From the WikiPedia ([[http://en.wikipedia.org/wiki/1_%28number%29]]):

'One is currently considered neither a prime number, nor a composite number - although it used to be considered prime.'

See ya,
bilderbikkel

: :

: : bool isPrime(const int& x)
: : {
: :   if(x == 2)
: :     return true;
: :   else if(x <= 1)
: :     return false;
: :   
: :   else if(x % 2 == 0)
: :     return false;
: : 
: : 
: :   for (int i=3; i<x/2; i+=2)
: :   {
: :     if (x % i == 0) 
: :       return false;
: :   }
: : 
: :   return true;
: : }
: : 

: :
: : 1 is not a prime number. Plus, prime numbers are natural numbers, thus not anything like 0, -1, -2, -3...
:
: Thanks for your correction. Indeed, negatives are not prime, but it depends on your definition if one is prime. From the WikiPedia ([[http://en.wikipedia.org/wiki/1_%28number%29]]):
:
: 'One is currently considered neither a prime number, nor a composite number - although it used to be considered prime.'
:
: See ya,
: bilderbikkel
:
:



In that case, x and i should be changed to unsigned int.

Another comment: there is no point in passing x as reference. As a rule of thumb, pass primitive data types (int, char, float etc) by value and everything else by reference.

: : :

: : : bool isPrime(const int& x)
: : : {
: : :   if(x == 2)
: : :     return true;
: : :   else if(x <= 1)
: : :     return false;
: : :   
: : :   else if(x % 2 == 0)
: : :     return false;
: : : 
: : : 
: : :   for (int i=3; i<x/2; i+=2)
: : :   {
: : :     if (x % i == 0) 
: : :       return false;
: : :   }
: : : 
: : :   return true;
: : : }
: : : 

: : :
: : : 1 is not a prime number. Plus, prime numbers are natural numbers, thus not anything like 0, -1, -2, -3...
: :
: : Thanks for your correction. Indeed, negatives are not prime, but it depends on your definition if one is prime. From the WikiPedia ([[http://en.wikipedia.org/wiki/1_%28number%29]]):
: :
: : 'One is currently considered neither a prime number, nor a composite number - although it used to be considered prime.'
: :
: : See ya,
: : bilderbikkel
: :
: :
:
:
:
: In that case, x and i should be changed to unsigned int.
:
: Another comment: there is no point in passing x as reference. As a rule of thumb, pass primitive data types (int, char, float etc) by value and everything else by reference.
:

My comment is that the for loop the condition should be stored in a constant varible or something as every time it tests the condition it is dividing x by two. Where as, if it were to store the test condition in a const int or whatever it would eliminate this process mind you it is completely irrevelent really and it is somewhat easier to read without it

This message was edited by Lundin at 2007-3-15 3:31:33

---

: : : :

: : : : bool isPrime(const int& x)
: : : : {
: : : :   if(x == 2)
: : : :     return true;
: : : :   else if(x <= 1)
: : : :     return false;
: : : :   
: : : :   else if(x % 2 == 0)
: : : :     return false;
: : : : 
: : : : 
: : : :   for (int i=3; i<x/2; i+=2)
: : : :   {
: : : :     if (x % i == 0) 
: : : :       return false;
: : : :   }
: : : : 
: : : :   return true;
: : : : }
: : : : 

: : : :
: : : : 1 is not a prime number. Plus, prime numbers are natural numbers, thus not anything like 0, -1, -2, -3...
: : :
: : : Thanks for your correction. Indeed, negatives are not prime, but it depends on your definition if one is prime. From the WikiPedia ([[http://en.wikipedia.org/wiki/1_%28number%29]]):
: : :
: : : 'One is currently considered neither a prime number, nor a composite number - although it used to be considered prime.'
: : :
: : : See ya,
: : : bilderbikkel
: : :
: : :
: :
: :
: :
: : In that case, x and i should be changed to unsigned int.
: :
: : Another comment: there is no point in passing x as reference. As a rule of thumb, pass primitive data types (int, char, float etc) by value and everything else by reference.
: :
:
: My comment is that the for loop the condition should be stored in a constant varible or something as every time it tests the condition it is dividing x by two. Where as, if it were to store the test condition in a const int or whatever it would eliminate this process mind you it is completely irrevelent really and it is somewhat easier to read without it
:


Yeah but it is a good point that I didn't think of. It will increase the efficiency of the code drastically. Here is a new version with correct data types and no reference.

bool isPrime(unsigned int x)
{
  if(x == 2)
    return true;
  else if(x < 2)
    return false;
  else if(x % 2 == 0)
    return false;


  unsigned int half_x = x / 2;
  unsigned int i;

  for(i=3; i<half_x; i+=2)
  {
    if (x % i == 0) 
      return false;
  }

  return true;
}

:

: bool isPrime(unsigned int x)
: {
:   if(x == 2)
:     return true;
:   else if(x < 2)
:     return false;
:   else if(x % 2 == 0)
:     return false;
: 
: 
:   unsigned int half_x = x / 2;
:   unsigned int i;
: 
:   for(i=3; i<half_x; i+=2)
:   {
:     if (x % i == 0) 
:       return false;
:   }
: 
:   return true;
: }
: 

:
Correct. I would even finish the loop at root_of_x, which is, for numbers > 4, less than half_x. Example: Half of 10000 is 5000, the square root of it is only 100.

: :

: : bool isPrime(unsigned int x)
: : {
: :   if(x == 2)
: :     return true;
: :   else if(x < 2)
: :     return false;
: :   else if(x % 2 == 0)
: :     return false;
: : 
: : 
: :   unsigned int half_x = x / 2;
: :   unsigned int i;
: : 
: :   for(i=3; i<half_x; i+=2)
: :   {
: :     if (x % i == 0) 
: :       return false;
: :   }
: : 
: :   return true;
: : }
: : 

: :
: Correct. I would even finish the loop at root_of_x, which is, for numbers > 4, less than half_x. Example: Half of 10000 is 5000, the square root of it is only 100.
:
:


To calculate the root would require sluggish float number algorithms. So unless the number entered is extremly high, that will only slow down the program.