shabbir's Avatar, Join Date: Jul 2004
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
pradeep's Avatar, Join Date: Apr 2005
Team Leader
Interesting, so we will find the factor of n within any of the number in sqrt(n) if not then its a prime number.
friendsforniraj's Avatar, Join Date: Nov 2006
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
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
friendsforniraj thats a good logic explained.
friendsforniraj's Avatar, Join Date: Nov 2006
Go4Expert Member
thank u sir
but ma name is niraj
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Quote:
Originally Posted by friendsforniraj
thank u sir
but ma name is niraj
I will try putting that from now on.
rahul.mca2001's Avatar, Join Date: Feb 2008
Ambitious contributor
why do we need a square root
asadullah.ansari's Avatar, Join Date: Jan 2008
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
oleber's Avatar, Join Date: Apr 2007
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.
oleber's Avatar, Join Date: Apr 2007
Go4Expert Member
for getting the prime number try

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

No devisions in here