## C and C++

Moderators: None (Apply to moderate this forum)
Number of posts: 94611

This Forum Only

a programme to display prime numbers Posted by wizad on 9 Mar 2007 at 10:17 AM
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
Re: a programme to display prime numbers Posted by subirkumarsao on 10 Mar 2007 at 2:22 AM
: 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.
Re: a programme to display prime numbers Posted by bilderbikkel on 10 Mar 2007 at 4:19 AM
:
: 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

Re: a programme to display prime numbers Posted by Lundin on 12 Mar 2007 at 1:47 AM
: :
: : 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;
}
```

Re: a programme to display prime numbers Posted by Gregry2 on 12 Mar 2007 at 5:41 AM
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
Re: a programme to display prime numbers Posted by bilderbikkel on 12 Mar 2007 at 6:31 AM
:
```: 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

Re: a programme to display prime numbers Posted by Lundin on 12 Mar 2007 at 7:26 AM
: :
```: : 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.
Re: a programme to display prime numbers Posted by bluj91 on 13 Mar 2007 at 6:13 PM
: : :
```: : : 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
Re: a programme to display prime numbers Posted by Lundin on 15 Mar 2007 at 3:30 AM
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;
}
```

Re: a programme to display prime numbers Posted by FDrache on 15 Mar 2007 at 5:49 AM
:
```: 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.

Re: a programme to display prime numbers Posted by Lundin on 15 Mar 2007 at 7:40 AM
: :
```: : 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.