programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Generating Number Pairs and GCD

Greenhorn
Posts: 2
• Number of slices to send:
Optional 'thank-you' note:
Problem: Given A,B print the number of pairs (a,b) such that GCD(a,b)=1 and 1<=a<=A and 1<=b<=B.

Solution (Brute Force Approach): In the below code, i have used brute force approach and it works fine. However the execution time is more 10 sec if A & B > 10^5

Alternative Solution: From my research i found out that finding prime factors of A & B will reduce the execution time considerably (< 3 sec), but i'm not sure how to apply it.

Need Help: Can anyone help me to arrive at the result with < 3 sec execution time?

Bartender
Posts: 1166
17
• 1
• Number of slices to send:
Optional 'thank-you' note:

Alternative Solution: From my research i found out that finding prime factors of A & B will reduce the execution time considerably (< 3 sec), but i'm not sure how to apply it.

Since you have not demonstrate this yourself (if you had you would not be asking for this help) presumably the "research" article(s) indicated how it should be applied. Could you post a references?

lowercase baba
Posts: 13089
67
• Number of slices to send:
Optional 'thank-you' note:
do you know how to find the prime factors of a number? I'd start with getting that to work.

Greenhorn
Posts: 2
• Number of slices to send:
Optional 'thank-you' note:
yes, i did that. I have 2 Lists which contains the prime factors of A & B.

But i don't know how to proceed further.

Marshal
Posts: 28239
95
• Number of slices to send:
Optional 'thank-you' note:
I should point out that knowing the prime factorizations of A and B only help in calculating GCD(A, B) and not with calculating GCD(a, b) for any other values of a and b.

At any rate, if you have lists of prime factors of A and B then the prime factors of GCD(A, B) are the intersection of those two lists. If you actually needed to calculate GCD(A, B) your task would be more complicated than that, but since you only need to know if it's equal to 1, you just need to know whether the intersection is empty or not.

fred rosenberger
lowercase baba
Posts: 13089
67
• Number of slices to send:
Optional 'thank-you' note:
knowing the prime factors of A and B should help you reduce the number of pairs of (a,b) you have to check. If A and B both have 7 as a factor, you can eliminate all a and b that are multiples of 7.

Further, you know that for all prime factors of A (assume 5 is one) that are NOT factors of B, then (5, b) is a pair you need, provided b%5 != 0.

I think...I've not proved this to myself.

Bartender
Posts: 5466
212
• Number of slices to send:
Optional 'thank-you' note:
hi John,

before embarking on a method involving primes, have you looked at the 'calculateGCD' implementation?
Sure you have some fast algorithm there (like Euclides' algorithm)?
Also: why are you using BigInteger? You construct these from integers and I can't think of any reason
why that would be beneficial.

Anyway: if you really want to go fast, then use Python. In all my solutions so far in the ProjectEuler,
every time I sent in a solution, proud of the fine code and the fast run time, there were these Python guys
doing it in just one line of code, taking only 0.001 picosecond.

Greetz,
Piet

Bartender
Posts: 10780
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:Also: why are you using BigInteger? You construct these from integers and I can't think of any reason
why that would be beneficial.

Well, one reason might be that BigInteger has a gcd() method (which does use Euclid's algorithm AFAIK).

It also has a very useful isProbablePrime() method.

I also suspect that the overhead of using BigIntegers is likely to be small compared to using logic such as Fred's to eliminate checks you don't need to make. But, TBH, I have no idea...

Winston

Piet Souris
Bartender
Posts: 5466
212
• Number of slices to send:
Optional 'thank-you' note:
Yes, I saw that BigInteger has a gcd method. I looked it up right after I sent my reply, one of these occasions
where you regret having sent a reply.

I've tested it, using the code that John supplied, both using int's and the Euclid gcd algorithm, and his code,
using BigIntegers. I've let a and b run from 1 to 10.000, only to see that the int-version took 22 seconds on
my laptop, the BigInteger one took 46 seconds. I'm not sure how John manages to get a run time of only 10 seconds
for a and b up to 100.000. Maybe his pc is way faster than my humble laptop.

Well, some simple optimizations are:

1) since gcd(a, b) = gcd(b, a) you can let b run from 1 to a
2) in the first loop 'for (a = 1; a <= MAX; a++)' set BigInteger ba = BigInteger.valueOf(a) before entering the b loop
3) you can store the values of gcd(a,b) in a HashMap, and in the routine, look up the in-between values. Of course, this limits
the a and b values that you can use, so it wouldn't work for arbitrary values of a and b.

But the BigInteger version works for arbitrary a and b, which is a big advantage.

For the prime number method, for down to earth ProjectEuler problems, I usually start with generating a HashMap and an
ArrayList of primes. Using the sieve of Erathotenes is a very fast method to do that.
Then, if you have found the primes of A, and store these in, say, a HashMap<Long, ArrayList<Long>>, then you can derive
the primes of multiples of A. Say for 2A, you look up the primes of 2, and add these to the list of primes of A.

Having such a list, finding the gcd of a and b boils down to intersecting the corresponding lists.
This too will not work for arbitrary a and b.

Well, that's what I can think of optimizations.

Greetz,
Piet

Winston Gutkowski
Bartender
Posts: 10780
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:For the prime number method, for down to earth ProjectEuler problems, I usually start with generating a HashMap and an
ArrayList of primes. Using the sieve of Erathotenes is a very fast method to do that.

For relatively small numbers, sure; but isProbablePrime() is also pretty darn fast for small p (probability) values. With p = 4, for example, if the number you supply is not prime, the method will return false on average 15 times out of 16, and it will execute very quickly. If it returns true, then you can try a deterministic solution (usually slower) to make sure that it really is prime.

And the time it takes is roughly proportional to the p value, so p=6 will take about 50% longer than p=4, but you reduce the chances of a "false true" to 1 in 64.

Winston

Marshal
Posts: 79263
377
• Number of slices to send:
Optional 'thank-you' note:
I am surprised that a Euclid's algorithm can take 10″ to run, even for 10⁴ runs. Does that mean you ran it 10⁸ times? Actually it would be approx 0.5×10⁸ runs for all pairs up to 10000. You realise that Euclid's algorithm is reasonably simple for you to implement yourself? Always use non‑negative numbers and give a positive result, so you may need Math#abs or your own absoluteValue method.

Sheriff
Posts: 3837
66
• Number of slices to send:
Optional 'thank-you' note:

fred rosenberger wrote:knowing the prime factors of A and B should help you reduce the number of pairs of (a,b) you have to check. If A and B both have 7 as a factor, you can eliminate all a and b that are multiples of 7.

I'm not getting this. Prime factors of A and B have nothing to do with prime factors of a and b, when 1 < a < A and 1 < b < B. Actually, I think there is a counterexample:

Let's have A=77, B=70, a=35, b=48. GDC(a,b) = 1, even though both A and B have 7 as a factor and a is a multiple of 7.

If both a and b are a multiple of 7, then their GDC is obviously at least 7, regardless of the prime factors of A and B.

I thing it should be possible to build the values of a and b from primes, in a process similar to the sieve of Eratosthenes - to avoid factorization. I haven't thought it through, though.

Piet Souris
Bartender
Posts: 5466
212
• Number of slices to send:
Optional 'thank-you' note:

Winston Gutkowski wrote:
For relatively small numbers, sure; but isProbablePrime() is also pretty darn fast for small p (probability) values. With p = 4, for example, if the number you supply is not prime, the method will return false on average 15 times out of 16, and it will execute very quickly. If it returns true, then you can try a deterministic solution (usually slower) to make sure that it really is prime.

And the time it takes is roughly proportional to the p value, so p=6 will take about 50% longer than p=4, but you reduce the chances of a "false true" to 1 in 64.

Winston

'isProbablePrime' sounds too uncertain for me to make use of it. In ProjectEuler, if you are supposed to send in
a solution in the range of 20 digits (no exception), then even being just 1 off is already counted as wrong.

@Campbell:
if you look at the code supplied, you see that there is a double loop, from 1 to 10.000 each, so the number of
GCD's is in the order of 10^8.

@John: one obvious improvement would be to generate an array of say, 10 million Integers first, including
the primes each is built from. That saves creating all these BI's in your double loop. Then you could find the
GCD by intersecting the accompanying primes-lists. So, something like HashMap<Integer, ArrayList<Integer>>.

For numbers larger than 10M, I think it is wise to do some investigations on the internet. It is amazing
how many facts, generating functions, whatever, there are concerning prime numbers.

Greetz,
Piet

fred rosenberger
lowercase baba
Posts: 13089
67
• Number of slices to send:
Optional 'thank-you' note:
Like i said..i hadn't thought it through..