我一直在尝试解决这个问题：https://codility.com/programmers/task/common_prime_divisors/
我让它在返回正确答案方面发挥作用，但对于较大的数字来说，它非常慢，我想看看是否有人能更好地更快地完成它，或者解释我可以优化它的方法。
bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0)
{
return false;
}
}
return true;
}
bool GetPrimeFactors(int valueA, int valueB)
{
if(valueA < 0 || valueB < 0)
return false;
int max = sqrt(std::max(valueA, valueB)) + 1;//sqrt(std::max(valueA, valueB));
std::vector<int> factors;
bool oneSuccess = false;
for(int i = 2; i <= max; i++)
{
bool remainderA = valueA % i == 0;
bool remainderB = valueB % i == 0;
if(remainderA != remainderB)
return false;
if(IsPrime(i))
{
//bool remainderA = valueA % i == 0;
// bool remainderB = valueB % i == 0;
if(remainderA != remainderB )
{
return false;
}
else if(!oneSuccess && remainderA && remainderB)
{
oneSuccess = true;
}
}
}
return true;
}
int solution(vector<int> &A, vector<int> &B) {
int count = 0;
for(size_t i = 0; i < A.size(); i++)
{
int valA = A[i];
int valB = B[i];
if(GetPrimeFactors(valA, valB))
++count;
}
return count;
}
您实际上不必找到数字的素数来决定它们是否具有相同的素数。
这是我为检查a和b是否具有相同的素因子而想出的一个通用算法。这将比素数因子a和b快得多。
- 如果是
a == b，则答案是true - 如果是
a == 1 || b == 1，则答案是false - 使用欧几里得算法来找到这两个数字的GCD。如果是
GCD == 1，则答案是false - 请注意，
GCD需要包含两个数字的所有素数才能使答案为真，因此检查newa = a/GCD和newb = b/GCD是否可以通过反复除以Euclid(newa, GCD)和Euclid(newb, GCD)而减为1，直到newa和newb达到成功的1，或者Euclid(newa, GCD)或Euclid(newb, GCD)返回失败的1
让我们看看这对于a=75，b=15是如何工作的：1） GCD=欧几里得（75，15）=152） newa=75/15=5，newb=15/15=1，用newb完成3） newa=5/欧几里得（5/15）=5/5=1成功！a=6，b=4如何：1） GCD=欧几里得（6,4）=22） newa=6/2=3，newb=4/2=23） 欧几里得（newa，2）=欧几里得（3，2）=1失败！a=2，b=16如何：1） GCD=欧几里得（2，16）=22） newa=2/2=1（很好），newb=16/2=83） newb=8/欧几里得（8,2）=8/2=44） newb=4/欧几里得（4,2）=4/2=25） newb=2/欧几里得（2，2）=2/2=1成功！
一个（相当琐碎的）优化（更新）：
bool IsPrime(int number)
{
if (number % 2 == 0)
{
return (number == 2);
}
int limit = sqrt(number);
for (int i = 3; i <= limit; i += 2)
{
if (number % i == 0)
{
return false;
}
}
return true;
}
基于vacawama答案的Java实现：
class Solution {
public int solution(int[] A, int[] B) {
int count = 0;
for(int i = 0; i < A.length; i++){
if(A[i] == B[i]) count++;
else if(A[i] == 1 || B[i] == 1) continue;
else{
int GCD = gcd(A[i], B[i]);
if(GCD == 1) continue;
int newA = A[i]/GCD;
int newB = B[i]/GCD;
if(checkDiv(newA, GCD) && checkDiv(newB, GCD)) count++;
}
}
return count;
}
public boolean checkDiv(int num, int gcd){
if(num == 1) return true;
else if(gcd == 1) return false;
else {
gcd = gcd(gcd, num);
num = num/gcd;
return checkDiv(num, gcd);
}
}
public int gcd(int a, int b){
if(b == 0) return a;
else return gcd(b, a % b);
}
}
在这里找到了很好且非常详细的解释：
假设两个数N和M，用素数分解它们，然后将N和M的GCD表示为P1 * P2 * P3 * P4 * ... Px（它们都是gcd(N,M)的素数）。然后，用它们的素数分别将N / gcd(N,M)和M / gcd(N,M)表示为N1 * N2 * N3 * ... Ny和M1 * M2 * M3 * ... Mz；则N和M可以表示如下。
N = (P1 * P2 * P3 ... Px) * N1 * N2 * N3 * ... Ny
M = (P1 * P2 * P3 ... Px) * M1 * M2 * M3 * ... Mz
由于(P1 * P2 * P3 ... Px)是gcd(N,M)，所以N和M共有的任何素数在(P1, P2, P3, ... Px)中总是至少出现一次。
换句话说，如果在(P1, P2, P3, ...Px)中找不到‘N/ gcd(N,M)’(N1, N2, N3 ... Ny)的任何素数，则它不是M的素数。因此，可以说N和M的素数集并不完全相同。
类似地，如果在(P1, P2. P3, ... Px)中找不到‘M / gcd(A,B)’(M1, M2, L3 ... Ly)的任何素数，则它不是N的素数，并且可以说N和M的素数集并不完全相同。
所以问题只是检查N1-Ny和M1-Mz中是否有任何一个从未出现在P1-Px中。
现在让我们想想这个。设X = N / gcd(N,M)，考虑gcd(gcd(N, M), X)。
目前，情况如下。
gcd(N,M): P1 * P2 * P3 ... Px
X : N1 * N2 * N3 ... Ny
如果gcd(N,M) % X == 0，则X的所有素数都包含在gcd(N,M)中。
如果不是，那么我们计算gcd(gcd(N,M), X)。如果这两个值的gcd仅为1，则意味着N1-Ny没有出现在P1-Px中；这意味着值CCD_ 62具有不与CCD_。
如果gcd大于1。然后我们计算X / gcd(gcd(N,M), X)并用它更新X用于下一轮。这意味着我们取出了构成gcd(gcd(N,M), X)的X的一些素数，并将其用于下一轮
如果此时gcd(N, M) % X == 0，则意味着X的所有素数都包含在gcd(N, M)中。如果没有，我们将再次执行与上面相同的操作。
上面@vacawama解决方案的python实现。
def gcd_division(a, b):
if not a%b:
return b
return gcd_division(b, a%b)
def prime_reduce(n, gcd):
na = n // gcd
ngcd = gcd_division(na, gcd)
if na == 1:
return True # success base case
elif ngcd == 1:
return False
return prime_reduce(na, ngcd)
def solution(A, B):
Z = len(A)
result = 0
for i in range(0, Z):
a, b = A[i], B[i]
if a == b:
result += 1
else:
gcd = gcd_division(a, b)
result += (prime_reduce(a, gcd) and prime_reduce(b, gcd))
return result
我用以下测试用例运行了它。
if __name__ == '__main__':
test_cases = (
(1, ([15, 10, 9], [75, 30, 5]) ),
(2, ([7, 17, 5, 3], [7, 11, 5, 2]) ),
(2, ([3, 9, 20, 11], [9, 81, 5, 13]) ),
)
for expected, args in test_cases:
got = solution(*args)
print('result', expected, got)
assert(expected == got)
它的100%https://app.codility.com/demo/results/training7KRXR3-FE5/
使用@vacawama答案的Javascript解决方案。编码 100%
function solution(A, B) {
function getGcd(a,b, res = 1) {
if (a === b) return res * a;
if (a % 2 === 0 && b % 2 === 0) return getGcd(a/2, b/2, 2 * res);
if (a % 2 === 0) return getGcd(a/2, b, res);
if (b % 2 === 0) return getGcd(a, b/2, res);
if (a > b) return getGcd(a-b, b, res);
else return getGcd(a, b-a, res);
}
const hasCommonPrimeDivisors = (a, b) => {
if (a === b) return true;
if (a === 1 || b === 1) return false;
let gcd = getGcd(a, b);
if (gcd === 1) return false;
while (a !== 1 || b !== 1) {
let newGcd;
if (a !== 1) {
newGcd = getGcd(a, gcd);
if (newGcd === 1) {
return false;
}
a = a / newGcd;
}
if (b !== 1) {
newGcd = getGcd(b, gcd);
if (newGcd === 1) {
return false;
}
b = b/newGcd;
}
}
return true;
}
let count = 0
A.forEach((a, index) => {
const b = B[index];
if (hasCommonPrimeDivisors(a, b)) {
count++;
}
})
return count;
}
对于数A[i]、B[i]的每对（总共Z对），其思想是用它们的共享素数集来减少A[i]和B[i]。
如果在这个过程结束时，减少的值不都等于1，那么最初组成A[i]和B[i]的素数集是不同的。
这是python代码，实现了O（Z*log（max（A）+max（B））^2）复杂性（和O（1）空间复杂性）。log（max（A）+max（B）^2部分有点难看，但它对应于还原操作。
def gcd(a, b):
if a < b:
r, s = b, a
else:
r, s = a, b
while s > 0:
r = r % s
r, s = s, r
return r
def solution(A, B):
res = 0
for i in range(len(A)):
g = gcd(A[i], B[i]) # set of prime divisors common to A[i] and B[i] is "contained" in g
A[i] = A[i] // g
B[i] = B[i] // g
k = gcd(g, A[i])
while k > 1:
A[i] = A[i] // k
k = gcd(g, A[i])
k = gcd(g, B[i])
while k > 1:
B[i] = B[i] // k
k = gcd(g, B[i])
if A[i] == 1 and B[i] == 1:
res += 1
return res