# CommonPrimeDivisors

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
function solution(A, B) { var gcd = function( a, b ){ if( a % b === 0 ){ return b; }else{ return gcd( b, a % b ); } }; var removeCommonPrimeDivisors = function( a, b ){ while( a != 1 ){ var gcd_value = gcd( a, b ); if( gcd_value == 1 ){ break; } a /= gcd_value; } return a; }; var hasSamePrimeDivisors = function( a, b ){ var gcd_value = gcd( a, b ); a = removeCommonPrimeDivisors( a, gcd_value); if ( a != 1 ){ return false; } b = removeCommonPrimeDivisors( b, gcd_value ); return b == 1; }; var solution = function(){ var count = 0; for( var i = 0; i < A.length; i++ ){ if(hasSamePrimeDivisors( A[ i ], B[ i ] ) ){ count++; } } return count; } return solution(); } |

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:

function solution(A, B);

that, given two non-empty zero-indexed 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] = 5

the function should return 1, because only one pair (15, 75) has the same set of prime divisors.

Assume that:

Z is an integer within the range [1..6,000];

each element of arrays A, B is an integer within the range [1..2,147,483,647].

Complexity:

expected worst-case time complexity is O(Z*log(max(A)+max(B))2);

expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.