https://codility.com/programmers/lessons/12-euclidean_algorithm/common_prime_divisors/
Explanation: Coming soon
// you can use includes, for example: // #include <algorithm> // you can write to stdout for debugging purposes, e.g. // cout << "this is a debug message" << endl; #include <stdio.h> #define LOG(...) //printf(__VA_ARGS__) int gcd(int a, int b) { LOG("--->gcd(%d, %d)\n", a, b); if (b > a) { auto t = a; a = b; b = t; } int t; while ((t = (a % b)) != 0) { a = b; b = t; LOG("------>gcd step (%d, %d)\n", a, b); } LOG("----------> gcd return %d\n", b); return b; } bool has_same_prime_divisors(int a, int b) { LOG("->has_same_prime_divisors(%d, %d)\n", a, b); int old_a = a; int old_b = b; if (b > a) { auto t = a; a = b; b = t; } bool re = false; if (a == b) { re = true; goto end; } if (b == 1) { re = false; goto end; } int _gcd; if ((_gcd = gcd(a, b)) != 1) { int a_temp = a; int b_temp = b; a /= _gcd; b /= _gcd; LOG("%d = {%d} * %d\n", a_temp, _gcd, a); LOG("%d = {%d} * %d\n", b_temp, _gcd, b); int _inner_gcd; while ((_inner_gcd = gcd(a, _gcd)) != 1) { a /= _inner_gcd; } if (a == 1) { while ((_inner_gcd = gcd(b, _gcd)) != 1) { b /= _inner_gcd; } re = b == 1; } } end: LOG("->has_same_prime_divisors(%d, %d) returns %d\n", old_a, old_b, re); return re; } int solution(vector<int> &A, vector<int> &B) { // write your code in C++14 (g++ 6.2.0) int re = 0; for (int i = 0; i < A.size(); ++i) { if (has_same_prime_divisors(A[i], B[i])) re++; } return re; }