A problem involving divisors
There are two numbers written on a board, A and B. If A and B are divisible by P, where P is a certain prime number, we can replace A and B with respectively A/P and B/P. Furthermore, if A is divisible by P, and B is divisible by P^2, we can replace A and B with A/P and B/(P^2). What two lowest-sum numbers can we get on a board? For the input 3 6, the output would be 1 2. For the input 70 84, the output would be 5 3.
I have no idea how to tackle this problem. Could someone help me out?
I have no idea how to tackle this problem. Could someone help me out?
You'd want a loop. The loop would go through all possible values of P and test whether A and B fall into the first or second condition for every value of P you go through. You'd start at P = 2, the smallest prime number possible, and work your way up.
Would be helpful to have a function that checks if a given value is a prime number or not, that way you can skip an iteration where your value isn't prime.
Once you have a P that does fit the criteria, that's your smallest P value.
I am, however, not finding this example sensical:
For 3 and 6, the prime number is 3 which divides 3, giving 1, and divides 6, giving 2.
However, 70 and 84 doesn't work. The P value here would be 14, dividing 70 to get 5. But even ignoring the fact that 14 isn't prime, 84 / 14 would be 6, not 3. And 14^2 doesn't divide 84. So I don't know where that example came from - its either wrong or I'm misinterpreting something.
Would be helpful to have a function that checks if a given value is a prime number or not, that way you can skip an iteration where your value isn't prime.
Once you have a P that does fit the criteria, that's your smallest P value.
I am, however, not finding this example sensical:
For the input 3 6, the output would be 1 2. For the input 70 84, the output would be 5 3. |
For 3 and 6, the prime number is 3 which divides 3, giving 1, and divides 6, giving 2.
However, 70 and 84 doesn't work. The P value here would be 14, dividing 70 to get 5. But even ignoring the fact that 14 isn't prime, 84 / 14 would be 6, not 3. And 14^2 doesn't divide 84. So I don't know where that example came from - its either wrong or I'm misinterpreting something.
prime factorize the GCD...
the gcd is 14, as noted in passing above.
that prime factors into 2 and 7
divide 70 by 2 until you can't anymore: 35
divide 84 by 2 until you cant anymore: 42 21
divide 35 by 7 until you cant anymore is 5
divide 21 by 7 until you can't anymore, is 3
5 and 3
however repeated gcd is probably a better approach: prime factoring is difficult.
if you divide both by 14, you get 5 and 6, as said. gcd 5 and 14 (done, is 1) and 6 and 14 (is 2) so 6/2 is 3... does that hold up?
the gcd is 14, as noted in passing above.
that prime factors into 2 and 7
divide 70 by 2 until you can't anymore: 35
divide 84 by 2 until you cant anymore: 42 21
divide 35 by 7 until you cant anymore is 5
divide 21 by 7 until you can't anymore, is 3
5 and 3
however repeated gcd is probably a better approach: prime factoring is difficult.
if you divide both by 14, you get 5 and 6, as said. gcd 5 and 14 (done, is 1) and 6 and 14 (is 2) so 6/2 is 3... does that hold up?
Last edited on
Ah, I must have misread. I was under the impression there would be only 1 division by the greatest prime GCD.
this is off in theoryland where I fail hard though. I would check that algorithm on a bunch of better examples or see if you can do a quick proof on it.
For 70 and 84,
- divide each by 7 gives 10 and 12
- divide the first by 2 and the second by 2^2 giving 5 and 3
so the example is fine.
I'd be inclined to find the prime factorisation of their gcd (which gives all common primes), then, for each of those primes, divide out as many as you can from each number, noting that the question doesn't allow you to use more than twice as many of the same factor from one as from the other.
For 70 and 84 the gcd is 14, which has prime factors 7 and 2.
7 goes into 70 once and 84 once, so you can divide one 7 out of each.
2 goes into 70 once and 84 twice, so you can divide one 2 out of the first and two 2s out of the second.
- divide each by 7 gives 10 and 12
- divide the first by 2 and the second by 2^2 giving 5 and 3
so the example is fine.
I'd be inclined to find the prime factorisation of their gcd (which gives all common primes), then, for each of those primes, divide out as many as you can from each number, noting that the question doesn't allow you to use more than twice as many of the same factor from one as from the other.
For 70 and 84 the gcd is 14, which has prime factors 7 and 2.
7 goes into 70 once and 84 once, so you can divide one 7 out of each.
2 goes into 70 once and 84 twice, so you can divide one 2 out of the first and two 2s out of the second.
Last edited on
Topic archived. No new replies allowed.