Well speaking about number of divisors of n ... all you need to do is to find the prime factorization of n.
An example: n = 12, which is 2x2x3. As you can see, there are 2 prime factors, one appears 2 times, and the other appears 1 time. So, the number of divisors will be: (2+1) * (1+1) = 3 x 2 = 6 Your example of 25 also applies, ... 25 = 5 x 5 ... there is only one prime, appearing twice. So number of divisors is: (2+1) = 3. To get ALL the divisors, it's as easy as trying all combination of prime multiplications (each can be used 0 times up to the number it appears in the prime factorization of n). -Lego On 6/27/07, mukesh tiwari <[EMAIL PROTECTED]> wrote: > > > ya you are right . this is project euler problem . > > until now i have found that i can determine how many devisiors of > number in sqrt(n) but what are the divisiors above aqrt(n) i am > not able to determine. > if sqrt(n) is perfect square and there are k factors upto sqrt(n) > then total number of divisiors will be (2*k-1) otherwise (2*k). > > i.e. 25 is perfect squre and sqrt(25)=5 .There are only two > divisiors 1 and 5 then total number of divisiors of 25 will (2*2-1)=3 > but here problem arise . after sqrt(n) i can not find what will be > other factors . > > if some how i can over come this problem than for each divisior of > number i have to find out all the prime factors and check out how > many of them are in form of 4k+1 and how many are of 4k+3 . for all 4k > +1 prime numbers i have to find > p=a^2+b^2. > > but still i don't know how much it will be efficient becoz till now i > haven't coded this problem . > > On Jun 26, 6:08 am, "Lego Haryanto" <[EMAIL PROTECTED]> wrote: > > This is most likely about a Project Euler problem. > > > > A tough one, I don't know how to get the result under 60s time > limit. To > > capture the Gaussian factors a+bi that divides an integer, I generated > pairs > > of a and b (which is relatively prime to each other), and for each, I > > observed the a^2+b^2 denominator to see the smallest n which can divide > > a^2+b^2, ... something like that. I'm sure you already note that if > a+bi is > > a factor, then a-bi is also a factor, and similiarly when a != b, b-ai > and > > b+ai are also Gaussian factors. > > > > My solution is very ugly but it does solve the problem in a little bit > over > > 60 seconds. > > > > I'm sure there exists more elegant solution for this. > > > > Best, > > -Lego > > > > On 6/22/07, mukesh tiwari <[EMAIL PROTECTED]> wrote: > > > > > > > > > hello everybody . > > > i want to know algorithm for finding gaussian factor of real > > > number . > > > like for 5 there are five gaussian factors > > > 1, 1+2i, 1-2i, 2+i, 2-i, 5 and there sum is 12 . so can any one help > > > me on this topic . i search lot on google but could not find any > > > anything . if u have any such kind of link so kindly send me . thnkx > > > in advance . > > > > -- > > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > > > -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
