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.";
: : : : 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:
[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...
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.'
: : [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 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.
Comments
: 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: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
: 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
: : 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.
: : : 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
: : : : [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]
: 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.
: : 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