การลบขั้นต่ำจากอาร์เรย์เพื่อทำให้ GCD Greater ใน Python

สมมติว่าเรามีรายการตัวเลข N; เราต้องหาจำนวนขั้นต่ำของการลบตัวเลขที่จำเป็นเพื่อให้ GCD ของตัวเลขที่เหลือมากกว่า GCD เริ่มต้นของตัวเลข N

ดังนั้น หากอินพุตเป็น [6,9,15,30] ผลลัพธ์จะเป็น 2 เนื่องจาก gcd เริ่มต้นคือ 3 ดังนั้นหลังจากลบ 6 และ 9 เราจะได้รับ gcd เป็น 15, 15> 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• INF :=1000001
• spf :=รายการที่มีองค์ประกอบ 0 ถึง INF
• กำหนดฟังก์ชัน sieve()
• สำหรับฉันในช่วง 4 ถึง INF เพิ่มขึ้น 2 ทำ
  • spf[i] :=2
• สำหรับผมในช่วง 3 ถึง INF ให้ทำ
  • ถ้า i^2> INF −
    • แตก
  • ถ้า spf[i] เหมือนกับ i แล้ว
    • สำหรับ j ในช่วง 2 * i เป็น INF ให้อัปเดตในแต่ละขั้นตอนโดย i ทำ
      • ถ้า spf[j] เหมือนกับ j แล้ว
        • spf[j] :=ฉัน
• กำหนดฟังก์ชัน calc_fact() นี่จะใช้เวลา x
• ret :=รายการใหม่
• ในขณะที่ x ไม่เหมือนกับ 1 ให้ทำ
  • ใส่ spf[x] ที่ส่วนท้ายของ ret
  • x :=x / spf[x] (รับเฉพาะส่วนจำนวนเต็ม)
• คืนสินค้า
• จากวิธีหลัก ให้ทำดังนี้ -
• ก :=0
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • g :=gcd(a[i], g)
• my_map :=แผนที่ใหม่
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • a[i] :=a[i] / g (รับเฉพาะส่วนจำนวนเต็ม)
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • p :=calc_fact(a[i])
  • s :=แผนที่ใหม่
  • สำหรับ j ในช่วง 0 ถึงขนาดของ p ให้ทำ
    • s[p[j]] :=1
  • สำหรับแต่ละ i ใน s ทำ
    • my_map[i] :=get(i, 0) จาก my_map + 1
• ขั้นต่ำ =10^9
• สำหรับแต่ละ i ใน my_map ให้ทำ
  • ก่อน :=ฉัน
  • วินาที :=my_map[i]
  • ถ้า (n - วินาที) <=ต่ำสุด แล้ว
    • ขั้นต่ำ :=n - วินาที
• ถ้าขั้นต่ำไม่ใช่ 10^9 แล้ว
  • ผลตอบแทนขั้นต่ำ
• มิฉะนั้น
  • คืน -1

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

[6, 9, 15, 30], 4

ผลลัพธ์

2