Problem

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:

    int solution(vector<int> &A, vector<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] = 5

the 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..100,000];

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

Note:

Recall: If P / D = K, then D x K = P. 

In the problem, K in the expression, "D * K = P" is not the same as K in the subscripts, A[K] and B[K].

20 = 2 x 2 x 5 with unique prime factors of 2 and 5 (ignoring the repeated 2). 

The main objective of the problem is to verify if the set of unique prime factors of both given numbers are exactly the same (ignoring repeated prime numbers in each set).

The variable K, occurs in two places in the problem description. In these two places, the variable K has two different meanings. 

The HCF of two numbers that are the same, is the same number. For example: the HCF of 180 and 180 is 180. HCF of 15 and 15 is 15. HCF of 10 and 10 is 10. HCF of 3 and 3 is 3.

The HCF can be the smaller of the two numbers. For example, the HCF of 80 and 240 is 80 (240 / 80 = 3). The HCF can be smaller than either number. 

The HCF of two numbers that do not have a common prime factor (other than 1), is 1. For example: the HCF of 3 and 10 is 1. HCF of 5 and 12 is 1.

Two Main Situations

There are two main situations, for the problem, which are: 

- situation where the unique prime factors are the same;

- situation where the unique prime factors are not the same.

Situation where Unique Prime Factors are not the Same

Example: Consider the numbers: 420 and 180. 

The factors of 420 are:

2, 3, 4, 5, 6, 7, 12, 14, 15, 20, 21, 24, 28, 30, 35, 40, 42, 60, 84, 105, 140, 210, 420

The product expression for 420 is:

420 = 2 x 2 x 3 x 5 x 7

The factors of 180 are:

2, 3, 4, 5, 6, 12, 15, 20, 30, 45, 60, 90, 180

The product expression for 180 is:

180 = 2 x 2 x 3 x 3 x 5 

The Highest Common Factor between 420 and 180 is 60, which is less than 180, the smaller of the two numbers. Looking at their product expressions, 7 in 420 is missing from 180. Put another way, 420 has an additional extra unique factor of 7. So, the sets of (unique) prime divisors of integers, 420 and 180 are not the same.

HCF = 60 = 2 x 2 x 3 x 5, with unique factors of {2, 3, 5}. Notice that the odd factor, 7 (in 420) is not among the unique factors of the HCF.

Situation with Same Unique Prime Factors (Example)

Consider the numbers: 420 and 210. 

The factors of 420 are:

2, 3, 4, 5, 6, 7, 12, 14, 15, 20, 21, 24, 28, 30, 35, 40, 42, 60, 84, 105, 140, 210, 420

The product expression for 420 is:

420 = 2 x 2 x 3 x 5 x 7

The factors of 210 are:

2, 3, 5, 6, 7, 14, 15, 21, 30, 35, 42, 60, 105, 210

The product expression for 210 is:

210 = 2 x 3 x 5 x 7 

The HCF of 420 and 210 is 210. The unique prime factors of 420 are {2, 3, 5, 7}. The unique prime factors of 210 are {2, 3, 5, 7}. The unique prime factors for 420 and 210 are exactly the same.

The unique prime factors are the same, because one or more repeating prime factors in one number, do not repeat as many times in the other number as they repeat in the former number. 2 repeats in 420 but does not repeat in 210. 

HCF = 210 = 2 x 3 x 5 x 7, with unique factors of {2, 3, 5, 7}. There is no odd prime factor in any of the given numbers.

Another Example where Unique Prime Factors are not the same

Consider the numbers: 420 and 28. 

The factors of 420 are:

2, 3, 4, 5, 6, 7, 12, 14, 15, 20, 21, 24, 28, 30, 35, 40, 42, 60, 84, 105, 140, 210, 420

The product expression for 420 is:

420 = 2 x 2 x 3 x 5 x 7

The factors of 28 are:

2, 7, 14, 28

The product expression for 28 is:

28 = 2 x 2 x 7 

The HCF of 420 and 28 is 28. The unique prime factors of 420 are {2, 3, 5, 7}. The unique prime factors of 28 are {2, 7}. The unique prime factors of 420 and 28 are not the same.

The unique prime factors are not the same, because one or more prime factors in one number, do not occur at all in the other number. 3 and 7 in 420 do not occur at all in 28. In other words, 3 x 7 = 35 in 420 does not occur at all in 28. 

HCF = 28 = 2 x 2 x 7, with unique factors of {2, 7}. Notice that the odd factors, of 3 and 5 are not among the unique factors of the HCF.

Strategy

Start by determining the HCF (GCD) of both given numbers (integers). 

If each of the given numbers and the HCF, have the same unique prime factors, then the two given numbers have the same unique prime factors.

For each of the numbers, check if the HCF of the number and the above HCF, have the same unique prime factors. If neither pair has the same unique prime factors, then the two given numbers do not have the same unique primes factors. If both pairs have the same unique prime factors, then the two given numbers have the same unique prime factors. Checking if a pair has the same unique primes factors, needs a loop.

Detecting Non-Unique Prime Factors using HCF (Illustration) 

HCF and the Given Numbers

Given Numbers of 420 and 180

The given numbers are 420 and 180. The HCF is 60. 

420 = 2 x 2 x 3 x 5 x 7, with unique factors of {2, 3, 5, 7}.

180 = 2 x 2 x 3 x 3 x 5, with unique factors of {2, 3, 5}.

These two sets of unique factors are not the same.

Beginning with 420: The HCF of 420 and 180 is 60.

The HCF of 420 and 60 is 60.

Let the given number, 420 change to 7 from 420 / 60 = 7.

7 is the odd factor in 420, so far as HCF of 60 is concerned.

The HCF of 7 and 60 is 1. The loop should not continue further.

Just after the loop ceases to continue, the new given number, 7 is not equal to 1.

This means that the two sets of unique prime factors for 420 and 60 are not the same.

420 = 2 x 2 x 3 x 5 x 7; 60 = 2 x 2 x 3 x 5. 

However, for the benefit of doubts:

Beginning this time with 180: The HCF of 420 and 180 is 60.

The HCF of 180 and 60 is 60.

Let the given number, 180 change to 3 from 180 / 60 = 3.

The HCF of 3 and 60 is 3.

Let the new given number, 3 change to 1 from 3 / 3 = 1. Stop the loop here.

And the new given number is 1.

This 1 is indicative that the two numbers, 180 and 60 have exactly the same unique prime factors.

180 = 2 x 2 x 3 x 3 x 5; 60 = 2 x 2 x 3 x 5.

However, since the previous loop proves that the two sets of unique prime factors, of the numbers 420 and 180 with the HCF 60 are not exactly the same, the conclusion is that the two sets of unique prime factors are not the same. 

Given Numbers of 420 and 210

The given numbers are 420 and 210. The HCF is 210.

420 = 2 x 2 x 3 x 5 x 7, with unique factors of {2, 3, 5, 7}.

210 = 2 x 3 x 5 x 7, with unique factors of {2, 3, 5, 7}.

These two sets of unique factors are exactly the same. 

Beginning with 420: The HCF of 420 and 210 is 210.

The HCF of 420 and 210 is 210.

Let the given number, 420 change to 2 from 420 / 210 = 2.

The HCF of 2 and 210 is 2.

Let the new given number, 2 change to 1 from 2 / 2 = 1. Stop the loop here.

And the new given number is 1.

This 1 is indicative that the two numbers, 420 and 210 have exactly the same unique prime factors.

420 = 2 x 2 x 3 x 5 x 7; 210 = 2 x 3 x 5 x 7.

Well, maybe 210 (second given number) and 210 (HCF) would indicate otherwise:

The HCF of 210 and 210 is 210.

Beginning this time with 210: The HCF of 210 and 210 is 210.

Let the given number, 210 change to 1 from 210 / 210 = 1. Stop the loop here.

And the new given number is 1.

This 1 is indicative that the two numbers, 210 and 210 have exactly the same unique prime factors.

210 = 2 x 3 x 5 x 7; 210 = 2 x 3 x 5 x 7. 

Since both loops indicate that the two numbers, 420 and 210 have the same unique prime factors with the HCF 210, it means that the two given numbers have exactly the same unique prime factors.

Given Numbers of 420 and 28

The given numbers are 420 and 28. The HCF is 28. 

420 = 2 x 2 x 3 x 5 x 7, with unique factors of {2, 3, 5, 7}.

28 = 2 x 2 x 7, with unique factors of {2, 7}.

These two sets of unique factors are not the same.

Beginning with 420: The HCF of 420 and 28 is 28.

The HCF of 420 and 28 is 28.

Let the given number, 420 change to 15 from 420 / 28 = 15.

15 = 3 x 5 is the product of all the odd factors in 420, so far as HCF of 28 is concerned.

The HCF of 15 and 28 is 1. The loop should not continue further.

Just after the loop ceases to continue, the new given number, 15 is not equal to 1.

This means that the two sets of unique prime factors for 420 and 28 are not the same.

420 = 2 x 2 x 3 x 5 x 7; 28 = 2 x 2 x 7. 

However, for the benefit of doubts:

Beginning this time with 28: The HCF of 420 and 28 is 28.

The HCF of 28 and 28 is 28.

Let the given number, 28 change to 1 from 28 / 28 = 1. Stop the loop here.

And the new given number is 1.

This 1 is indicative that the two numbers, 28 and 28 have exactly the same unique prime factors.

28 = 2 x 2 x 7; 28 = 2 x 2 x 7.

However, since the previous loop proves that the two sets of unique prime factors, of the numbers 420 and 28 with the HCF 28 are not exactly the same, the conclusion is that the two sets of unique prime factors are not the same.

Given Numbers of 15 and 75

The given numbers are 15 and 75. The HCF is 15. 

15 = 3 x 5, with unique factors of {3, 5}.

75 = 3 x 5 x 5, with unique factors of {3, 5}.

These two sets of unique factors are exactly the same.

Beginning with 15: The HCF of 15 and 75 is 15.

The HCF of 15 and 15 is 15.

Let the given number, 15 change to 1 from 15 / 15 = 1. Stop the loop here.

And the new given number is 1.

This 1 is indicative that the two numbers, 15 and 15 have exactly the same unique prime factors.

15 = 3 x 5; 15 = 3 x 5 

Well, maybe 75 (second given number) and 15 (HCF) would indicate otherwise:

Beginning this time with 75: The HCF of 15 and 75 is 15.

The HCF of 75 and 15 is 15.

Let the given number, 75 change to 3 from 75 / 15 = 3.

The HCF or 3 and 15 is 3.

Let the new given number, 3 change to 1 from 3 / 3 = 1. Stop the loop here.

And the new given number is 1.

This 1 is indicative that the two numbers, 75 and 15 have exactly the same unique prime factors.

75 = 3 x 5 x 5; 15 = 3 x 5

Since both loops indicate that the two numbers, 15 and 75 have the same unique prime factors with the HCF 15, it means that the two given numbers have exactly the same unique prime factors. 

Given Numbers of 10 and 30

The given numbers are 10 and 30. The HCF is 10.

10 = 2 x 5, with unique factors of {2, 5}.

30 = 2 x 3 x 5, with unique factors of {2, 3, 5}.

These two sets of unique factors are not exactly the same. 

Beginning with 10: The HCF of 10 and 30 is 10.

The HCF of 10 and 10 is 10.

Let the given number, 10 change to 1 from 10 / 10 = 1. Stop the loop here.

And the new given number is 1.

This 1 is indicative that the two numbers, 10 and 10 have exactly the same unique prime factors.

10 = 2 x 5; 10 = 2 x 5

Well, maybe 30 (second given number) and 10 (HCF) would indicate otherwise:

Beginning this time with 30: The HCF of 10 and 30 is 10.

The HCF of 30 and 10 is 10.

Let the given number, 30 change to 3 from 30 / 10 = 3.

The HCF of 3 and 10 is 1. The loop should not continue further.

Just after the loop ceases to continue, the new given number, 3 is not equal to 1.

This means that the two sets of unique prime factors for 30 and 10 are not the same.

30 = 2 x 3 x 5; 10 = 2 x 5 

Since the previous loop proves that the two sets of unique prime factors, of the numbers 10 and 10 with the HCF 10 are the same, and the second loop proves that the two sets of unique prime factors, of the numbers 10 and 10 with the HCF 10 are different, then the conclusion is that the two sets of unique prime factors are not the same.

Given Numbers of 3 and 5

The given numbers are 3 and 5. The HCF is 1. 

3 = 3, with unique factors of {3}.

5 = 5, with unique factors of {5}.

These two sets of unique factors are not the same.

Beginning with 3: The HCF of 3 and 5 is 1.

The HCF of 3 and 1 is 1. The loop should not continue further.

Just after the loop ceases to continue, the given number, 3 is not equal to 1.

This means that the two sets of unique prime factors for 3 and 1 are not the same.

3 = 3; 1 = 1 

However, for the benefit of doubts:

Beginning this time with 5: The HCF of 3 and 5 is 1.

The HCF of 5 and 1 is 1. The loop should not continue further.

Just after the loop ceases to continue, the given number, 5 is not equal to 1.

This means that the two sets of unique prime factors for 5 and 1 are not the same.

5 = 5; 1 = 1

Since the previous loop proves that the two sets of unique prime factors, of the numbers 3 and 1 with the HCF 1, are not the same, and the second loop also proves that the two sets of unique prime factors, of the numbers 5 and 1 with the HCF 1 are different, then the conclusion is definitely that the two sets of unique prime factors are not the same.

How to detect Non-Unique Prime Factors, when given Two Integers

Start by determining the HCF (GCD) of both given numbers (integers). 

If each of the given numbers and the HCF, have the same unique prime factors, then the two given numbers have the same unique prime factors.

For each of the numbers, check if the HCF of the number and the above HCF, have the same unique prime factors. If neither pair has the same unique prime factors, then the two given numbers do not have the same unique primes factors. If both pairs have the same unique prime factors, then the two given numbers have the same unique prime factors. Checking if a pair has the same unique primes factors, needs a loop. 

Coding

The procedure above can be put into coding as follows:

The output is:

    1 

for true. The explanation for the code segment (for loop) to answer the queries, is left as an exercise for the reader.

Important: The reader must use the hasSamePrimeDivisors() function, to verify for himself/herself the solution. That is, substitute 15 and 75 for ‘a’ and b respectively; then 10 and 30 for ‘a’ and b respectively; and then 9 and 5 for ‘a’ and b respectively, and for each case, follow what is happening in the code. The same thing can be done for 420/180, 420 /210 and 420/28. 

At app.codility.com/programmers the scoring and detected time complexity for this solution() is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(Z * log(max(A) +  max(B))²) 

Thanks for reading.