Solution to Common-Prime-Divisors by codility | Code Says
http://www.cnblogs.com/easonliu/p/4463882.html
判断两个数是否有相同的素数约数。首先求出公约数gcd_val，那么gcd_val里应该包含了common prime divisor，下面分别判断a跟b与gcd_val的公约数是不是有自己的非common prime divisor的prime divisor。
public int solution(int[] A, int[] B) {
int ans = 0;
for (int i = 0; i < A.length; i++) {
if (common(A[i], B[i])) {
ans++;
}
}
return ans;
}
private boolean common(int x, int y) {
int d = gcd(x, y);
return commonGCD(d, x) && commonGCD(d, y);
}
private boolean commonGCD(int x, int y) {
int d = gcd(x, y);
while (d != 1) {
y /= d;
d = gcd(x, y);
}
return x % y == 0;
}
private int gcd(int n, int m) {
int r = n % m;
while (r != 0) {
n = m;
m = r;
r = n % m;
}
return m;
}
http://codility-lessons.blogspot.com/2015/03/lesson-10-commonprimedivisors.html
if (gcd_tmp == 1){
Read full article from Solution to Common-Prime-Divisors by codility | Code Says
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(int A[], int B[], int Z);
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.
Question: https://codility.com/demo/take-sample-test/common_prime_divisors
http://www.martinkysel.com/codility-commonprimedivisors-solution/
http://www.martinkysel.com/codility-commonprimedivisors-solution/
def gcd(x, y):
# Compute the greatest common divisor
if x%y == 0:
return y;
else:
return gcd(y, x%y)
def hasSamePrimeDivisors(x, y):
gcd_value = gcd(x, y) # The gcd contains all
# the common prime divisors
while x != 1:
x_gcd = gcd(x, gcd_value)
if x_gcd == 1:
# x does not contain any more
# common prime divisors
break
x /= x_gcd
if x != 1:
# If x and y have exactly the same common
# prime divisors, x must be composed by
# the prime divisors in gcd_value. So
# after previous loop, x must be one.
return False
while y != 1:
y_gcd = gcd(y, gcd_value)
if y_gcd == 1:
# y does not contain any more
# common prime divisors
break
y /= y_gcd
return y == 1
def solution(A, B):
count = 0
for x,y in zip(A,B): // if x<0 or y<0 throw ex;
if hasSamePrimeDivisors(x,y):
count += 1
return count
http://www.cnblogs.com/easonliu/p/4463882.html
判断两个数是否有相同的素数约数。首先求出公约数gcd_val，那么gcd_val里应该包含了common prime divisor，下面分别判断a跟b与gcd_val的公约数是不是有自己的非common prime divisor的prime divisor。
1 def gcd(x, y): 2 # Compute the greatest common divisor 3 if x%y == 0: 4 return y; 5 else: 6 return gcd(y, x%y) 7 8 def hasSamePrimeDivisors(x, y): 9 gcd_value = gcd(x, y) # The gcd contains all 10 # the common prime divisors 11 12 while x != 1: 13 x_gcd = gcd(x, gcd_value) 14 if x_gcd == 1: 15 # x does not contain any more 16 # common prime divisors 17 break 18 x /= x_gcd 19 if x != 1: 20 # If x and y have exactly the same common 21 # prime divisors, x must be composed by 22 # the prime divisors in gcd_value. So 23 # after previous loop, x must be one. 24 return False 25 26 while y != 1: 27 y_gcd = gcd(y, gcd_value) 28 if y_gcd == 1: 29 # y does not contain any more 30 # common prime divisors 31 break 32 y /= y_gcd 33 34 return y == 1https://github.com/acprimer/Codility/blob/master/src/Lesson10/CommonPrimeDivisors.java
public int solution(int[] A, int[] B) {
int ans = 0;
for (int i = 0; i < A.length; i++) {
if (common(A[i], B[i])) {
ans++;
}
}
return ans;
}
private boolean common(int x, int y) {
int d = gcd(x, y);
return commonGCD(d, x) && commonGCD(d, y);
}
private boolean commonGCD(int x, int y) {
int d = gcd(x, y);
while (d != 1) {
y /= d;
d = gcd(x, y);
}
return x % y == 0;
}
private int gcd(int n, int m) {
int r = n % m;
while (r != 0) {
n = m;
m = r;
r = n % m;
}
return m;
}
http://codility-lessons.blogspot.com/2015/03/lesson-10-commonprimedivisors.html
int check(int a, int gcd_ab)
{
//check if all the prime divisors of 'a' can be found
//in the prime divisors of gcd(a,b).
int rest = a / gcd_ab;
//if gcd(a, b) % rest == 0, that means all the prime divisors
//of 'rest' is included in the prime divisors of gcd(a,b).
while (gcd_ab % rest != 0){
int gcd_tmp = gcd(gcd_ab, rest);
//if gcd(a,b) have 1 as the gcd with rest larger,
//that means 'a / gcd(a,b)' contains some prime divisor that is not
//found in the prime divisors of gcd(a,b).if (gcd_tmp == 1){
return 0;
}
rest /= gcd_tmp;
}
return 1;
}
int solution(int A[], int B[], int Z)
{
int cnt = 0;
int i;
for (i = 0; i < Z; i++){
int gcd_ab = gcd(A[i], B[i]);
if (check(A[i], gcd_ab) && check(B[i], gcd_ab)){
cnt++;
}
}
return cnt;
}
http://www.martinkysel.com/codility-commonprimedivisors-solution/Read full article from Solution to Common-Prime-Divisors by codility | Code Says
