ค้นหาการดำเนินการสูงสุดเพื่อลด N ถึง 1 ใน Python

สมมุติว่าเรามีตัวเลข P และ Q สองตัว และสร้างเป็นตัวเลข N =(P!/Q!) เราต้องลด N ถึง 1 โดยดำเนินการตามจำนวนการดำเนินการสูงสุดที่เป็นไปได้ ในแต่ละการดำเนินการ เราสามารถแทนที่ N ด้วย N/X เมื่อ N หารด้วย X ลงตัว เราจะคืนค่าจำนวนการดำเนินการสูงสุดที่เป็นไปได้

ดังนั้น หากอินพุตเป็น A =7, B =4 ผลลัพธ์จะเป็น 4 เนื่องจาก N คือ 210 และตัวหารคือ 2, 3, 5, 7

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

• ไม่มี :=1000005

• ปัจจัย :=อาร์เรย์ขนาด N และเติมด้วย 0

• จากวิธีหลัก ให้ทำดังนี้ −

• สำหรับผมอยู่ในช่วง 2 ถึง N ทำ

  • ถ้าตัวประกอบ[i] เท่ากับ 0 แล้ว

    • สำหรับ j ในช่วง i ถึง N ให้อัปเดตในแต่ละขั้นตอนโดย i ทำ

      • ปัจจัย[j] :=ปัจจัย[j / i] + 1

• สำหรับผมอยู่ในช่วง 1 ถึง N ทำ

  • ปัจจัย[i] :=ปัจจัย[i] + ปัจจัย[i - 1];

• ปัจจัยส่งคืน[a] - ปัจจัย[b]

ตัวอย่าง

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

N = 1000005
factors = [0] * N;
def get_prime_facts() :
   for i in range(2, N) :
      if (factors[i] == 0) :
         for j in range(i, N, i) :
            factors[j] = factors[j // i] + 1
   for i in range(1, N) :
      factors[i] += factors[i - 1];
get_prime_facts();
a = 7; b = 4;
print(factors[a] - factors[b])

อินพุต

7,4

ผลลัพธ์

4