
import
java.util.*;
public
class
GFG {
static
int
primes[] =
new
int
[
1000006
];
static
int
gcd(
int
a,
int
b)
{
if
(b ==
0
)
return
a;
else
return
gcd(b, a % b);
}
static
void
preprocess()
{
for
(
int
i =
1
; i <=
1000000
; i++)
primes[i] = i;
for
(
int
i =
2
; i * i <=
1000000
; i++) {
if
(primes[i] == i) {
for
(
int
j =
2
* i;
j <=
1000000
; j += i) {
if
(primes[j] == j)
primes[j] = i;
}
}
}
}
static
int
Steps(
int
x,
int
m)
{
int
steps =
0
;
boolean
flag =
false
;
while
(x >
1
) {
if
(primes[x] > m) {
flag =
true
;
break
;
}
x /= primes[x];
steps++;
}
if
(flag)
return
-
1
;
return
steps;
}
static
int
minimumSteps(
int
x,
int
y,
int
m)
{
preprocess();
int
g = gcd(x, y);
x = x / g;
y = y / g;
int
x_steps = Steps(x, m);
int
y_steps = Steps(y, m);
if
(x_steps == -
1
|| y_steps == -
1
)
return
-
1
;
return
x_steps + y_steps;
}
public
static
void
main(String args[])
{
int
X =
160
;
int
Y =
180
;
int
M =
10
;
System.out.println(
minimumSteps(X, Y, M));
}
}
0 comments:
Post a Comment