Hi, Mukesh, I had the similar issue on your example of 8.
My algorithm is actually a little bit "reversed" from what you have. You
see, I started with generating (a, b) pairs, and then look for the possible
n which can divide a+bi (or a-bi, or b+ai, or b-ai).
In your example case, 4+4i is indeed a factor of 8. In fact, gcd(4, 4) =
4. And 4^2 + 4^2 is 32. If you take into account of the gcd and use it to
divide the 32, you'll end up with 8 (which is the first n which can divide
4+4i). After you see the first term (in this case, 8), you can see that
4+4i also divides, 16, 24, 32, 40, ... etc.
Generally, given a and b, ... the first n which divides a+bi is: a^2+b^2 div
gcd(a, b). Please ponder this a little bit, and then you'll see some
pattern. You'll also see the relationship of a+bi and k(a+bi), when k is a
positive integer > 1.
I just want to reiterate that my algorithm is not fast at all, again it runs
a little bit over a minute for this one.
Best,
-Lego
On 6/28/07, mukesh tiwari <[EMAIL PROTECTED]> wrote:
>
>
> Hi Lego i need your help . i am not able to find any efficient
> algorithm to find the divisiors of integer in gaussian ring . so i
> used a brute force methode to find all the gaussian divisiors of
> integer . here is my code ..
>
> #include<stdio.h>
> #include<math.h>
>
> main()
> {
> int n,x,y,k,w;
> while(scanf("%d",&n)!=EOF)
> {
> k=sqrt(n);
> for(x=1;x<=k;x++)
> {
> for(y=1;y<=k;y++)
> {
> w=x*x+y*y;
> if(x!=y && n%w==0)
> printf("%d + i%d\n",x,y);
> else if( x==y && (n*x)%w==0)
> printf("%d + i%d\n",x,y);
> }
> }
> }
> }
>
> my algorithm is
> x^2+y^2=n . in order to find all the complex divisiors i loop from
> 1<=x<=sqrt(n)
> and 1<=y<=sqrt(n) . My program generates quite good result but not as
> accurate as i need .
> if i give input 13 output is 2+3i and 3+2i but if i give 8 it gives
> 1+i and 2+2i but i think 4+ 4i is also a factor but my program can't
> find it becoz i am iterating upto sqrt(8)=2 so plz help me . if u
> have any some good tutorial or link plz send me as i am new in feild
> of number theory .
> thnkx .
>
> On Jun 27, 10:08 pm, "Lego Haryanto" <[EMAIL PROTECTED]> wrote:
> > 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)
>
>
> >
>
--
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
-~----------~----~----~----~------~----~------~--~---
