0
Go4Expert Founder
There is other method also which does not require sqrt.

Quote:
Originally Posted by wiki
One need not actually calculate the square root; once one sees that the quotient is less than the divisor, one can stop
0
Interesting, so we will find the factor of n within any of the number in sqrt(n) if not then its a prime number.
0
Go4Expert Member
let me tell you the logic now
it is very simple
look if k is any no.
then k can be represented as k=i*j
where i and are k's factor
now i varies from 1to k
and j varies from k to 1
but for prime no. we check for i=2 to k/2
acordingly j will varies from (k/2) to 2
now if 2 is a factor of k
then automatically k/2 is also a factor and so on
that is when i increases, j decreases
so we continue like this then there is condition that both i and j becomes equal
so i*i=k
so i=sqrt(k)
but if k is not a square of any no. then i increases upto a integer just less than sqrt iof k
thats all what i did
now try this problem
for a given no. print all its prime factors that is
if input is 12 out put should be 2*2*3
using the hint that the lowest factor of any no. other than one is always prime
try it
0
Go4Expert Founder
friendsforniraj thats a good logic explained.
0
Go4Expert Member
thank u sir
but ma name is niraj
0
Go4Expert Founder
Quote:
Originally Posted by friendsforniraj
thank u sir
but ma name is niraj
I will try putting that from now on.
0
Ambitious contributor
why do we need a square root
0
TechCake
Quote:
Originally Posted by friendsforniraj
let me tell you the logic now
it is very simple
look if k is any no.
then k can be represented as k=i*j
where i and are k's factor
now i varies from 1to k
and j varies from k to 1
but for prime no. we check for i=2 to k/2
acordingly j will varies from (k/2) to 2
now if 2 is a factor of k
then automatically k/2 is also a factor and so on
that is when i increases, j decreases
so we continue like this then there is condition that both i and j becomes equal
so i*i=k
so i=sqrt(k)
but if k is not a square of any no. then i increases upto a integer just less than sqrt iof k
thats all what i did
now try this problem
for a given no. print all its prime factors that is
if input is 12 out put should be 2*2*3
using the hint that the lowest factor of any no. other than one is always prime
try it
Excellent explaination. Now any one can understand either he is new or experience
0
Go4Expert Member
for(j=2;j<=sqrt(i);j++)

is similar to

for(j=2;j*j <= i;j++)

so, no sqrt in here since it is really slow. At least if was some years ago.
0
Go4Expert Member
for getting the prime number try

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

No devisions in here