Problem Statement
You are given two nonnegative integers P and Q. Your task is to make the integers equal in as many steps as possible. In each step you can do one of two things:
- Add any prime number to P.
- Subtract any prime number from Q.
If it's not possible to make P and Q equal, return -1. Otherwise, return a nonnegative integer: the maximum (not minimum!) number of steps you can make.
Definition
- Class:
- MaximumMoves
- Method:
- getMaximumMoves
- Parameters:
- long, long
- Returns:
- long
- Method signature:
- long getMaximumMoves(long P, long Q)
- (be sure your method is public)
Notes
- Primes are positive integers with exactly two positive integer divisors. The smallest few primes are 2, 3, 5, 7, 11, 13, ...
- In particular, the numbers 0 and 1 are not prime numbers.
Constraints
- P will be between 0 and 10^18, inclusive.
- Q will be between 0 and 10^18, inclusive.
Examples
5
9
Returns: 2
In one optimal solution we first subtract 2 from Q and then add 2 to P. After these two steps both numbers are equal (both are 7).
5
10
Returns: 2
In one optimal solution we first subtract 2 from Q and then add 3 to P. After these two steps both numbers are equal (both are 8).
5
6
Returns: -1
There's no way to make these P and Q equal.
10
2
Returns: -1
1000000000
121212121212451
Returns: 60605560606225
14298210421838
366827767865386
Returns: 176264778721774
14349877241189
439506955362064
Returns: 212578539060437
184373633107319
14407595129473
Returns: -1
14450418078845
272248849202242
Returns: 128899215561698
272248849202242
272248849202242
Returns: 0
0
0
Returns: 0
0
1
Returns: -1
3111919587526
27670731543192
Returns: 12279405977833
314413235881563
11198639114940588
Returns: 5442112939529512
315193194295161
8773079306639286
Returns: 4228943056172062
990147540778667093
999683106896341869
Returns: 4767783058837388
5
8
Returns: 1
10
10
Returns: 0
10
5
Returns: -1
10
100
Returns: 45
0
1000000000000000000
Returns: 500000000000000000
27
10
Returns: -1
12
12
Returns: 0
1
1
Returns: 0
0
6
Returns: 3
5
5
Returns: 0
3
5
Returns: 1
5
100
Returns: 47
2
3
Returns: -1
4
4
Returns: 0
1
4
Returns: 1
2
2
Returns: 0
8
8
Returns: 0
13
13
Returns: 0
5
3
Returns: -1
2
105
Returns: 51
1
7
Returns: 3
6
9
Returns: 1
1
1000000000000000000
Returns: 499999999999999999
10
27
Returns: 8
100
100
Returns: 0
6
6
Returns: 0
3
3
Returns: 0
2
10000000000000000
Returns: 4999999999999999
1
100000000000000000
Returns: 49999999999999999
1000000000
1000000000000000000
Returns: 499999999500000000