Số lần loại bỏ tối thiểu từ mảng để GCD lớn hơn trong Python

Cho một danh sách N số, ta cần tìm số lượng số cần loại bỏ tối thiểu sao cho GCD (ước chung lớn nhất) của các số còn lại lớn hơn GCD ban đầu của N số.

Ví dụ, nếu đầu vào là [6, 9, 15, 30], kết quả sẽ là 2 vì GCD ban đầu là 3, sau khi loại bỏ 6 và 9 ta được GCD = 15, và 15 > 3.

Thuật toán giải quyết

• INF := 100001.
• spf (smallest prime factor) là mảng từ 0 đến INF.
• Hàm sieve() (sàng Eratosthenes):
  • Với i từ 4 đến INF, bước 2: spf[i] := 2.
  • Với i từ 3 đến INF:
    • Nếu i² > INF thì thoát.
    • Nếu spf[i] == i (là số nguyên tố):
      • Với j từ 2*i đến INF, bước i: nếu spf[j] == j thì spf[j] := i.
• Hàm calc_fact(x):
  • ret := [].
  • Trong khi x != 1:
    • Thêm spf[x] vào ret.
    • x := x // spf[x].
  • Trả về ret.
• Từ hàm chính:
  • Tính g := GCD của toàn bộ mảng.
  • Chia mỗi phần tử cho g.
  • Dùng my_map đếm tần suất các ước nguyên tố.
  • Tìm minimum := n - max_frequency.
  • Nếu minimum != 10⁹ trả về minimum, ngược lại trả về -1.

Ví dụ minh họa

from math import gcd as __gcd

INF = 100001
spf = [i for i in range(INF)]

def sieve():
    for i in range(4, INF, 2):
        spf[i] = 2
    for i in range(3, INF):
        if i ** 2 > INF:
            break
        if spf[i] == i:
            for j in range(2 * i, INF, i):
                if spf[j] == j:
                    spf[j] = i

def calc_fact(x):
    ret = []
    while x != 1:
        ret.append(spf[x])
        x = x // spf[x]
    return ret

def minRemove(a, n):
    g = 0
    for i in range(n):
        g = __gcd(a[i], g)
    my_map = {}
    for i in range(n):
        a[i] = a[i] // g
    for i in range(n):
        p = calc_fact(a[i])
        s = {}
        for j in range(len(p)):
            s[p[j]] = 1
        for i in s:
            my_map[i] = my_map.get(i, 0) + 1
    minimum = 10 ** 9
    for i in my_map:
        second = my_map[i]
        if (n - second) <= minimum:
            minimum = n - second
    if minimum != 10 ** 9:
        return minimum
    else:
        return -1

a = [6, 9, 15, 30]
n = len(a)
sieve()
print(minRemove(a, n))  # 2

Đầu vào

[6, 9, 15, 30], 4

Đầu ra

2