# a programme to display prime numbers

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

## Comments

• : 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; [red]//should be: cin>>NUM[/red]
: for(int i=2;i<=NUM;i++) [red]//should be: for(int i=2;i<NUM;i++)[/red]
: {
: 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; [red]//should be: cin>>NUM[/red]
: : for(int i=2;i<=NUM;i++) [red]//should be: for(int i=2;i<NUM;i++)[/red]
: : {
: : 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:

[code]
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;
}
[/code]
• [b][red]This message was edited by Gregry2 at 2007-3-12 5:47:35[/red][/b][hr]
[b][red]This message was edited by Gregry2 at 2007-3-12 5:44:11[/red][/b][hr]
: : :
: : : int r=0;
: : : cin<<NUM; [red]//should be: cin>>NUM[/red]
: : : for(int i=2;i<=NUM;i++) [red]//should be: for(int i=2;i<NUM;i++)[/red]
: : : {
: : : 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:
:
: [code]
: 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;
: }
: [/code]
:

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

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

return true;
}
[/code]

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
• : [code]
: bool isPrime(const int& x)
: {
: [blue]if(x == 2)
: return true;
: else if(x <= 1)
: return false;
: [/blue]
: else if(x % 2 == 0)
: return false;
:
:
: for (int i=3; i<x/2; i+=2)
: {
: if (x % i == 0)
: return false;
: }
:
: return true;
: }
: [/code]
:
: 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_(number)]]):

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

See ya,
bilderbikkel

• : : [code]
: : bool isPrime(const int& x)
: : {
: : [blue]if(x == 2)
: : return true;
: : else if(x <= 1)
: : return false;
: : [/blue]
: : else if(x % 2 == 0)
: : return false;
: :
: :
: : for (int i=3; i<x/2; i+=2)
: : {
: : if (x % i == 0)
: : return false;
: : }
: :
: : return true;
: : }
: : [/code]
: :
: : 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_(number)]]):
:
: '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.
• : : : [code]
: : : bool isPrime(const int& x)
: : : {
: : : [blue]if(x == 2)
: : : return true;
: : : else if(x <= 1)
: : : return false;
: : : [/blue]
: : : else if(x % 2 == 0)
: : : return false;
: : :
: : :
: : : for (int i=3; i<x/2; i+=2)
: : : {
: : : if (x % i == 0)
: : : return false;
: : : }
: : :
: : : return true;
: : : }
: : : [/code]
: : :
: : : 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_(number)]]):
: :
: : '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
• [b][red]This message was edited by Lundin at 2007-3-15 3:31:33[/red][/b][hr]
: : : : [code]
: : : : bool isPrime(const int& x)
: : : : {
: : : : [blue]if(x == 2)
: : : : return true;
: : : : else if(x <= 1)
: : : : return false;
: : : : [/blue]
: : : : else if(x % 2 == 0)
: : : : return false;
: : : :
: : : :
: : : : for (int i=3; i<x/2; i+=2)
: : : : {
: : : : if (x % i == 0)
: : : : return false;
: : : : }
: : : :
: : : : return true;
: : : : }
: : : : [/code]
: : : :
: : : : 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_(number)]]):
: : :
: : : '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.

[code]
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;
}
[/code]

• : [code]
: 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 4, less than half_x. Example: Half of 10000 is 5000, the square root of it is only 100.

• : : [code]
: : 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 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.

• Read here prime numbers

Sign In or Register to comment.

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!