ধরা যাক দুটি সংখ্যা P এবং Q আছে যারা N = P!/Q! তৈরি করে। আমাদের N কে 1 এ রিডিউস করতে হবে সর্বোচ্চ অপারেশন দিয়ে। প্রতিটি অপারেশনে N কে N/X দিয়ে রিপ্লেস করা যায় যদি N, X দিয়ে বিভাজ্য হয়। সর্বোচ্চ অপারেশন সংখ্যা রিটার্ন করুন।
যেমন, A=7, B=4 হলে N=210, ডিভাইসর: 2,3,5,7 → আউটপুট 4।
সমাধানের ধাপসমূহ (সieve-রূপে প্রাইম ফ্যাক্টর গণনা)
- N := 1000005, factors[N] := 0 দিয়ে ভরুন
- for i in 2..N: if factors[i]==0: for j in i..N step i: factors[j] = factors[j//i] + 1
- for i in 1..N: factors[i] += factors[i-1] (প্রিফিক্স সম)
- উত্তর = factors[a] - factors[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
