|
|
back to boardMost of the time spent to find prime divisors. Probably you can optimize it. Try to seek with step=2 instead of 1 for example ;)
Edited by author 07.04.2004 20:04 maybe you can compute the primes with Eratostene's sieve...
I think not. I think that the main problem is with the algorithm itself. It is just a little bit optimized
O(sqrt(n)). What is the normal way of finding solutions for
|k1*p - k2*q| = 1? (k1 and k2 should be found).
Edited by author 08.04.2004 14:42 ap mod bp = cp, c<b, if cp=0 then b=1 and p==gcd(ap, bp)
Recurrent algorithm:
A(1)=p, B(0)=q
C(i)=A(i) mod B(i), A(i+1)=B(i), B(i+1)=C(i)
As gcd(p,q)==1, we get C(i)=1. Then lets write equations sequence:
A(1)-X(1)*B(1)=C(1)
A(2)-X(2)*B(2)=C(2)
...
A(i)-X(i)*B(i)=1
Please note that A(1)==p. Write down coefficient of A(1) in the final equation, and we'll get K such as p*K+q*K2=1. I guess it's the same algorith than called "extended euqlidian" somewhere in this forum. Thank you very much !!!!!
You way is very good !!!!! Can you tell me the method of finding
k1 and k2 in
a*k1 + b*k2 = 1, where gcd(a,b)=1 ????
Please, help !!!!!!!!!! Euclid extended algorithme for GCD |
|
|
