Most 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.

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

Thank you very much !!!!!
You way is very good !!!!!