# C++ programming on prime numbers

1. Feb 18, 2014

### 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?

2. Feb 18, 2014

### 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.

3. Feb 18, 2014

### smart_worker

#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?

4. Feb 18, 2014

### Staff: Mentor

Use [noparse]
Code (Text):

[/noparse] tags:

Code (Text):
#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.

5. Feb 18, 2014

### D H

Staff Emeritus
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).

6. Feb 18, 2014

### smart_worker

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

7. Feb 18, 2014

### D H

Staff Emeritus
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.

Last edited: Feb 18, 2014
8. Feb 18, 2014

### smart_worker

it is a prime number

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

9. Feb 18, 2014

### Staff: Mentor

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.