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)
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
