Question

c++code for prime and composite numbers?

Answer 1

ceive of aristothenes.Or O(N^2) procedure which checks for divisors

Answer 2

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int a;
cin>>a;
if(a%2!=0)
cout<<"Number is prime:"<<endl;
else
cout<<"composite"<<endl;



getch();
}

Answer 3

this is odd even, not prime composite.Do you know what a prime number is?

Answer 4

lol...i got...this..))

Answer 5

u see...the logic behind this.....every prime numbers expect 2 are not divisible by 2

Answer 6

the only prob with this code...is that it will show.. 2 as composite...))

Answer 7

yeah,, but there are numbers non-divisible by 2 which are composite

Answer 8

i need u clear it....hw

Answer 9

As you wish.. your algorithm is incorrect anyway

Answer 10

yes.....i never thought of it

Answer 11

can u correct me..plzz

Answer 12

One thing you can do is.Take every number, and search for a divisor, if you find one, then this number is not prime, if you don't find any it is.This is an Θ(Ν*sqrt(N)) algorithm

Answer 13

i knw this can be done..easily by looping...but i have nt studied that

Answer 14

what do you mean you haven't studied it? Just do it :P

Answer 15

i mean...That chapter is yet to come...for me..

Answer 16

loops?

Answer 17

@Yahoo! you can try citation if you need..It is slightly more complicated, but it works faster

Answer 18

i dont knw that...._

Answer 19

It's simple.. wanna explain? :)

Answer 20

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int a,i;
int flag=0;
cout<<"enter any number";
cin>>a;
for(i=2;i<=a/2;i++)
{
if(a%i==0)
{
flag++;
break;
}
}
if(flag!=0)
cout<<"Number is prime:"<<endl;
else
cout<<"Number is composite"<<endl;
getch();
}

Answer 21

no need to check up to a/2..You can check up to sqrt(N) and this is why:

Byu the fundamental theorem of arithmetics, every number is analysed in a unique way as a product of two numbers, so every number has at least two divisors, if both of them are bigger than it's square root then their product is bigger than the number itself, which is not possible, so your algorithm is of the class O(sqrrt(N)).

Answer 22

hm...@compute compiling was success...but when i typed 9 it says that it is prime

Answer 23

@Yahoo! actualy I typed dis code by my logic I didn't check it by run...so I don't know why dis gives it prime bcoz logic is true...now I don't have TC on my dis OS so u try to solve dis problm by own....

Answer 24

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


void main()
{
clrscr();
int n,i,flag=1;
cout<<"Enter any number:";
cin>>n;


for(i=2;i<=n/2;++i)
{
if(n%i==0)
{
flag=0;
break;
}
}
if(flag)
cout<<"\n"<<n<<" is a Prime number";
else
cout<<"\n"<<n<<" is not a Prime number";
getch();
}

Answer 25

@yahoo is it working...means U had written "if(flag) den print"...I think condition is not given properly...and rest r same as my code den why my code gives d wrong output...

Answer 26

and then lord created functions..

Answer 27

in each of the code written, are u guys checking for divisors up to n/2? .... beacause you don't need to go that high... you can go up to \(\large \sqrt{n} \) ....

Answer 28

It depends on the size of the input as to what method you want to use. If you need all of the sequential primes in a region, a sieving method is advisable (for example, the Sieve of Eratosthenes).

If you need to only know whether that specific number is prime, you can use what's called Trial Division (divide the number by all [prime] numbers below the square root to check for divisibility - this works because if a number is divisible by another above the square root, there is another divisor below it).

If the numbers are expected to be quite large, there are faster methods to determine if it's probably prime. Miller-Rabin, for example.


Going on the assumption that you only need small primes and that there won't be a large number of tests performed, you're probably looking for the simplest method, that is Trial Division.

http://en.wikipedia.org/wiki/Trial_division
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

If any of those are overwhelming, try searching by the names for tutorials specifically for beginners or ask specific questions here.