A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.
A prime D is called a prime divisor of a positive integer P if there exists a positive integer K such that D * K = P. For example, 2 and 5 are prime divisors of 20.
You are given two positive integers N and M. The goal is to check whether the sets of prime divisors of integers N and M are exactly the same.
For example, given:
- N = 15 and M = 75, the prime divisors are the same: {3, 5};
- N = 10 and M = 30, the prime divisors aren't the same: {2, 5} is not equal to {2, 3, 5};
- N = 9 and M = 5, the prime divisors aren't the same: {3} is not equal to {5}.
Write a function:
class Solution { public int solution(int[] A, int[] B); }
that, given two non-empty arrays A and B of Z integers, returns the number of positions K for which the prime divisors of A[K] and B[K] are exactly the same.
For example, given:
A[0] = 15 B[0] = 75 A[1] = 10 B[1] = 30 A[2] = 3 B[2] = 5the function should return 1, because only one pair (15, 75) has the same set of prime divisors.
Write an efficient algorithm for the following assumptions:
- Z is an integer within the range [1..6,000];
- each element of arrays A and B is an integer within the range [1..2,147,483,647].
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
// write your code in Java SE 8
}
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if () {
}
}
return result;
}
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if () {
result++;
}
}
return result;
}
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
}
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if () {
result++;
}
}
return result;
}
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
int quotient1 = 0;
while (quotient1 != 1) {
quotient1 = getGcd(num, gcd);
num /= quotient1;
}
}
rp
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if () {
result++;
}
}
return result;
}
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
int quotient1 = 0;
while (quotient1 != 1) {
quotient1 = getGcd(num, gcd);
num /= quotient1;
}
}
private int getDivisor() {
int quotient
}
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if () {
result++;
}
}
return result;
}
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
int quotient1 = 0;
while (quotient1 != 1) {
quotient1 = getGcd(num, gcd);
num /= quotient1;
}
}
private int getDivisor(int gcd, int num) {
int quotient = 0;
while (quotient != 1) {
quotient = getGcd(num, gcd);
num /= quotient;
}
return num;
}
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if () {
result++;
}
}
return result;
}
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
return getDivisor(gcd, num1) == 1 && getDivisor(gcd, num2);
}
private int getDivisor(int gcd, int num) {
int quotient = 0;
while (quotient != 1) {
quotient = getGcd(num, gcd);
num /= quotient;
}
return num;
}
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if (isSameDivisors(A[idx], B[idx])) {
result++;
}
}
return result;
}
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
return getDivisor(gcd, num1) == 1 && getDivisor(gcd, num2);
}
private int getDivisor(int gcd, int num) {
int quotient = 0;
while (quotient != 1) {
quotient = getGcd(num, gcd);
num /= quotient;
}
return num;
}
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if (isSameDivisors(A[idx], B[idx])) {
result++;
}
}
return result;
}
// Check whether the sets of prime divisors of integers N and M are exactly the same.
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
return getDivisor(gcd, num1) == 1 && getDivisor(gcd, num2);
}
private int getDivisor(int gcd, int num) {
int quotient = 0;
while (quotient != 1) {
quotient = getGcd(num, gcd);
num /= quotient;
}
return num;
}
// Euclidean algorithm.
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
Solution.java:20: error: bad operand types for binary operator '&&' return getDivisor(gcd, num1) == 1 && getDivisor(gcd, num2); ^ first type: boolean second type: int 1 error
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if (isSameDivisors(A[idx], B[idx])) {
result++;
}
}
return result;
}
// Check whether the sets of prime divisors of integers N and M are exactly the same.
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
return getDivisor(gcd, num1) == 1 && getDivisor(gcd, num2) == 1;
}
private int getDivisor(int gcd, int num) {
int quotient = 0;
while (quotient != 1) {
quotient = getGcd(num, gcd);
num /= quotient;
}
return num;
}
// Euclidean algorithm.
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if (isSameDivisors(A[idx], B[idx])) {
result++;
}
}
return result;
}
// Check whether the sets of prime divisors of integers N and M are exactly the same.
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
return getDivisor(gcd, num1) == 1 && getDivisor(gcd, num2) == 1;
}
private int getDivisor(int gcd, int num) {
int quotient = 0;
while (quotient != 1) {
quotient = getGcd(num, gcd);
num /= quotient;
}
return num;
}
// Euclidean algorithm.
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A, int[] B) {
int result = 0;
for (int idx = 0; idx < A.length; idx++) {
if (isSameDivisors(A[idx], B[idx])) {
result++;
}
}
return result;
}
// Check whether the sets of prime divisors of integers N and M are exactly the same.
private boolean isSameDivisors(int num1, int num2) {
int gcd = getGcd(num1, num2);
return getDivisor(gcd, num1) == 1 && getDivisor(gcd, num2) == 1;
}
private int getDivisor(int gcd, int num) {
int quotient = 0;
while (quotient != 1) {
quotient = getGcd(num, gcd);
num /= quotient;
}
return num;
}
// Euclidean algorithm.
private int getGcd(int num1, int num2) {
if (num1 % num2 == 0) {
return num2;
} else {
return getGcd(num2, num1 % num2);
}
}
}
The solution obtained perfect score.