Skip to content

Latest commit

 

History

History
163 lines (124 loc) · 4.33 KB

12.2 CommonPrimeDivisors.md

File metadata and controls

163 lines (124 loc) · 4.33 KB
Raw

Lesson_12 Euclidean algorithm

P12.2 CommonPrimeDivisors

Check whether two numbers have the same prime divisors.

  • P12.2 质因子个数

判断两个数是否有相同的质因子

大于1的自然数中，除了1和它本身以外不再有其他因数的数为质数，也称为素数。前6个质数分别是2、3、5、7、11和13。

质数D被称为正整数P的质因子，如果存在一个正整数K，使得D*K=P。例如，2和5是20的质因子。

给定两个正整数N和M，判断这2个整数的质因子集合是否完全相同。

例如，给定： N=15，M=75，质因子集合相同：3，5； N=10，M=30，质因子集合不同：前者为2，5，后者为2，3，5； N=9，M=5，质因子集合不同：3不等于5；

编写函数：

def solution(A, B)

给定两个非空的由Z个正整数组成的数组A和B，则返回A[K]和B[K]的质因子集合完全相同的位置K的个数。

例如，给定：A[0]=15，A[1]=10，A[2]=3；B[0]=75，B[1]=30，B[2]=5

函数应该返回1，因为只有当K为0时，（15，75）具有相同的质因子集合。

假定：

  1. Z是区间[1，6000]中的整数；
  2. 数组A，B的每个元素都是区间[1，2147483647]内的整数；

  • 解题思路

首先计算两个数的最大公约数，然后判断这2个数中是否含有最大公约数中没有的因子。

  • Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 12：Euclidean algorithm
# P 12.2 CommonPrimeDivisors


def prime(a, b):
    """
    返回正整数a的质因子集合
    :param a: 正整数
    :return: 返回质因子集合
    """
    start = 2
    while a != 1 and b != 1:
        if not a % start:
            if not b % start:  # a,b相同的质因子start
                a_num = a
                b_num = b
                while a - int(a) == 0:  # 把相同的质因子一次性删除
                    a_num = a
                    a /= start
                while b - int(b) == 0:  # 把相同的质因子一次性删除
                    b_num = b
                    b /= start
                a = a_num
                b = b_num
            else:  # a能被start整除，b不能
                break
        else:
            if not b % start:  # b能被start整除，a不能
                break
            else:  # 都不能被start整除
                start += 1
    if a == b:
        return True
    else:
        return False


def solution_base(A, B):
    """
    返回数组A和B组成的数对含有相同的质因子集合相同的个数,时间复杂度O(Z * log(max(A) + max(B))**2) or O(Z * (max(A) + max(B))**(1/2))
    :param A: 数组
    :param B: 数组
    :return: 返回相同的个数
    """
    count = 0
    for i, j in zip(A, B):
        if i == j:
            count += 1
        else:
            if prime(i, j):
                count += 1
    return count

#########################################


def gcd(a, b):
    """
    计算a和b的最大公约数，利用欧几里得算法——辗转相除法
    :param a: 整数
    :param b: 整数
    :return: a和b的最大公约数
    """
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


def judge(a, b):
    """
    判断a中是否存在b中不存在的因子
    :param a: 正整数
    :param b: 正整数
    :return: 存在返回True，不存在返回False
    """
    p = gcd(a, b)
    while p != 1:
        a //= p
        p = gcd(a, b)
    if a == 1:
        return False
    else:
        return True


def solution(A, B):
    """
    返回数组A和B组成的数对含有相同的质因子集合相同的个数
    首先得到A和B的最大公约数P，然后再判断A、B中是否存在P中不存在的因数， 时间复杂度O(Z * log(max(A) + max(B))**2)
    :param A: 数组
    :param B: 数组
    :return: 返回相同的个数
    """
    count = 0
    for i, j in zip(A, B):
        if i == j:
            count += 1
        else:
            p = gcd(i, j)
            # 判断A、B中是否存在P中不存在的因数
            if not judge(i, p) and not judge(j, p):
                count += 1
    return count

  • 结果

image