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) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
