পাইথনে N থেকে 1 কমাতে সর্বাধিক অপারেশন খুঁজুন

ধরুন আমাদের দুটি সংখ্যা P এবং Q আছে এবং তারা একটি সংখ্যা N =(P!/Q!) গঠন করে। আমাদের সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন সম্পাদন করে N 1 থেকে কমাতে হবে। প্রতিটি ক্রিয়াকলাপে, যখন N X দ্বারা বিভাজ্য হয় তখন একজন N-কে N/X দিয়ে প্রতিস্থাপন করতে পারে। আমরা সম্ভাব্য সর্বাধিক সংখ্যক অপারেশন ফেরত দেব।

সুতরাং, যদি ইনপুটটি A =7, B =4 এর মত হয়, তাহলে আউটপুট 4 হবে কারণ N 210 এবং ভাজক 2, 3, 5, 7।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

N :=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