C/C++ C++ programming on prime numbers

[smart_worker]

this is the program which i wrote:

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void prime(int p)
{
if(p==0||p==1)
{
cout<<"neither prime nor composite"<<endl;
getch();
exit(1);
}
for(int i=2;i<p/2;i++)
{
if(p%i==0)
{
cout<<"composite"<<endl;
break;
}
else
cout<<"prime"<<endl;
}
}
void main()
{
int n;
clrscr();
cout<<"enter a number:"<<endl;
cin>>n;
prime(n);
getch();
}


it is not working for some numbers like 9,5,2,etc..

if i input 9
output is :

composite
prime

if i input 5
nothing is displayed


i debugged and no errors came
what exactly is wrong with this code?

 

[Hypersphere]

That output looks right for that code. Let's look at your two cases to see what the program actually does.

If p=9, p/2=4 (remember integer division). Due to the test in the for loop, you will test the values i=2 and i=3. In the case of i=2, 9%2=1 and it prints prime no matter what the later tests will give. For i=3, 9%3=0 and it prints composite. You probably don't want to print prime until you've verified that no numbers covered in the loop are factors of p.

If p=5, p/2=2. This means that the for loop won't run at all, since 2 isn't less than 2. You probably do want to run the loop at least once.

 

[smart_worker]

That output looks right for that code. Let's look at your two cases to see what the program actually does.

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void prime(int p)
{
int count=1;
if(p==0||p==1)
{
cout<<"neither prime nor composite"<<endl;
getch();
exit(1);
}
for(int i=2;i<=p/2;i++)
{
if(p%i==0)
count++;
}
if(count>=2)
cout<<"not a PRIME NUMBER"<<endl;
else
cout<<"PRIME NUMBER"<<endl;
}
void main()
{
int n;
clrscr();
cout<<"enter a number:"<<endl;
cin>>n;
prime(n);
getch();
}


now is it correct?

 

[Borek]

Use [noparse]

[/noparse] tags:

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

void prime(int p)
{
   int count=1;

   if(p==0||p==1)
   {
      cout<<"neither prime nor composite"<<endl;
      getch();
      exit(1);
   }
   for(int i=2;i<=p/2;i++)
   {
      if (p%i==0)
         count++;
   }
   if(count>=2)
      cout<<"not a PRIME NUMBER"<<endl;
   else
      cout<<"PRIME NUMBER"<<endl;
}

void main()
{
   int n;

   clrscr();
   cout<<"enter a number:"<<endl;
   cin>>n;
   prime(n);
   getch();
}

For the code readability, correct formatting is paramount.

 

[D H]

now is it correct?

Strictly speaking, it's not correct. All it takes is one number to divide p with zero remainder and p is not prime. Your program will happen to have at least two divisors, but that's because your loop go to and including p/2. There's no reason to do that. Once you find one such divisor you know the number cannot be prime. Exit the loop immediately. There's no reason to go all the way to p/2. You only need to go up to and including sqrt(p). While the difference between p/2 and sqrt(p) is small for small numbers, it's not small at all for bit numbers. For example, a limit of p/2 means checking 500,000,000,019 numbers in the case p=1,000,000,000,039. A limit of sqrt(p) means you only need to check 1,000,000 numbers to see that 1,000,000,000,039 is indeed a prime. (And you can reduce this by a factor of two if you check 2 and then only check odd numbers).

 

[smart_worker]

Strictly speaking, it's not correct. All it takes is one number to divide p with zero remainder and p is not prime. Your program will happen to have at least two divisors, but that's because your loop go to and including p/2. There's no reason to do that. Once you find one such divisor you know the number cannot be prime. Exit the loop immediately. There's no reason to go all the way to p/2. You only need to go up to and including sqrt(p). While the difference between p/2 and sqrt(p) is small for small numbers, it's not small at all for bit numbers. For example, a limit of p/2 means checking 500,000,000,019 numbers in the case p=1,000,000,000,039. A limit of sqrt(p) means you only need to check 1,000,000 numbers to see that 1,000,000,000,039 is indeed a prime. (And you can reduce this by a factor of two if you check 2 and then only check odd numbers).

anyways for small numbers<100 i am getting correct results

and for bit numbers as you said for 1,000,000,000,039 i have to use longint instead of int

 

[D H]

The same argument applies to 2147483647 (which does fit within an int). Try this number. Your program takes an inordinate amount of time to say that this is a prime number. That is not acceptable. Ending your loop at 46340 rather than 1073741823 (in this case) would make your program 23,000 times faster.

BTW, you need to get a better compiler. Given your include files and your arcane use of void main, I suspect you are using Turbo C++. You should get a compiler that was written in this millennium. There are plenty of free compilers around. There is *no* reason to use Turbo C++ anymore.

 

[smart_worker]

2147483647

it is a prime number

if my program is too slow i can make use of INLINE function.

 

[Borek]

if my program is too slow i can make use of INLINE function.

It won't change much.

The fastest operation is the one never performed. D H told you how to implement it in your case, but apparently your prefer to not listen to the good advice.