Số lần xóa tối thiểu khỏi mảng để làm cho GCD Lớn hơn trong Python

Giả sử chúng ta có một danh sách gồm N số; chúng ta phải tìm số lần loại bỏ các số nhỏ nhất được yêu cầu để GCD của các số còn lại lớn hơn GCD ban đầu của N số.

Vì vậy, nếu đầu vào là [6,9,15,30], thì đầu ra sẽ là 2 vì gcd ban đầu là 3, vì vậy sau khi loại bỏ 6 và 9, chúng ta có thể nhận được gcd là 15, 15> 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

INF:=100001
spf:=một danh sách có các phần tử từ 0 đến INF
Xác định hàm sàng ()
đối với tôi trong phạm vi 4 đến INF, tăng thêm 2, thực hiện
- spf [i]:=2
đối với tôi trong phạm vi 3 đến INF, hãy thực hiện
- nếu tôi ^ 2> INF -
  - break
- nếu spf [i] giống với i, thì
  - cho j trong phạm vi 2 * i thành INF, cập nhật từng bước theo i, thực hiện
    - nếu spf [j] giống với j, thì
      - spf [j]:=i
Xác định một hàm calc_fact (). Điều này sẽ mất x
ret:=một danh sách mới
trong khi x không giống với 1, hãy thực hiện
- chèn spf [x] vào cuối ret
- x:=x / spf [x] (chỉ lấy phần nguyên)
trả lời lại
Từ phương thức chính, hãy làm như sau -
g:=0
đối với tôi trong phạm vi từ 0 đến n, thực hiện
- g:=gcd (a [i], g)
my_map:=một bản đồ mới
đối với tôi trong phạm vi từ 0 đến n, thực hiện
- a [i]:=a [i] / g (chỉ lấy phần nguyên)
đối với tôi trong phạm vi từ 0 đến n, thực hiện
- p:=calc_fact (a [i])
- s:=một bản đồ mới
- đối với j trong phạm vi từ 0 đến kích thước của p, thực hiện
  - s [p [j]]:=1
- đối với mỗi tôi trong s, thực hiện
  - my_map [i]:=get (i, 0) trong tổng số my_map + 1
tối thiểu =10 ^ 9
đối với mỗi tôi trong my_map, hãy thực hiện
- đầu tiên:=i
- thứ hai:=my_map [i]
- if (n - second) <=Minimum, then
  - tối thiểu:=n - giây
nếu tối thiểu không phải là 10 ^ 9, thì
- lợi nhuận tối thiểu
nếu không,
- trả về -1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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 = dict()
   for i in range(n):
      a[i] = a[i] // g
   for i in range(n):
      p = calc_fact(a[i])
      s = dict()
      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:
      first = i
      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))

Đầu vào

[6, 9, 15, 30], 4

Số lần xóa tối thiểu khỏi mảng để làm cho GCD Lớn hơn trong Python

Ví dụ

Đầu vào

Đầu ra