Already a member?

shabbir

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

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

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

friendsforniraj thats a good logic explained.

friendsforniraj

thank u sir
but ma name is niraj

shabbir

Quote:

Originally Posted by friendsforniraj
thank u sir
but ma name is niraj

I will try putting that from now on.

rahul.mca2001

why do we need a square root

asadullah.ansari

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

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

for getting the prime number try

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

No devisions in here

shabbir Go4Expert Founder
29Nov2006,18:02	#11
	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 Team Leader
29Nov2006,18:16	#12
	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 Go4Expert Member
2Dec2006,17:57	#13
	let me tell you the logic now it is very simple look if k is any no. then k can be represented as k=ij 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 ii=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 223 using the hint that the lowest factor of any no. other than one is always prime try it

shabbir Go4Expert Founder
4Dec2006,10:45	#14
	friendsforniraj thats a good logic explained.

friendsforniraj Go4Expert Member
5Dec2006,17:40	#15
	thank u sir but ma name is niraj

Already a member?

Not a member yet?

Search Go4Expert

Latest Forum Topics

Find Us On Facebook

Latest Articles

shabbir Go4Expert Founder
6Dec2006,11:13	#16
	Quote: Originally Posted by friendsforniraj thank u sir but ma name is niraj I will try putting that from now on.

rahul.mca2001 Ambitious contributor
6Mar2008,13:53	#17
	why do we need a square root

asadullah.ansari TechCake
7Mar2008,20:19	#18
	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=ij 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 ii=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 223 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 Go4Expert Member
8Mar2008,12:51	#19
	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 Go4Expert Member
8Mar2008,12:54	#20
	for getting the prime number try http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes No devisions in here

User Name:		Save
Password