SPOJ - SITB - Funny Prime Factorization Tutorial

Problem Description here

প্রব্লেমটিতে একটা সংখ্যা দেয়া থাকবে যার প্রাইম ফ্যাক্টরগুলো বের করতে বলা হয়েছে।


সল্যুশন আইডিয়াঃ

আমরা সাধারণত প্রাইম ফ্যাক্টরাইজ করি কীভাবে? প্রাইম জেনারেট করে স্কয়ার রুট পর্যন্ত প্রাইমগুলো দিয়ে কেটে কেটে! সেটার (মানে আমি -_-) মূলত এই সোজা শাপটা প্রব্লেম দিয়েছে ই যাতে তোমার এই সল্যুশন TLE খায়!

তাহলে উপায় কী!

সবগুলো সংখ্যার ক্ষুদ্রতম প্রাইম ফ্যাক্টর বের করে নাও। যেমনঃ ৮ এর ক্ষুদ্রতম প্রাইম ফ্যাক্টর ২ , ১৫ এর ক্ষুদ্রতম প্রাইম ফ্যাক্টর ৩।

মনে করো, আমি N = ৬০ এর প্রাইম ফ্যাক্টর বের করতে চাই। ৬০ পর্যন্ত সবার ক্ষুদ্রতম প্রাইম ফ্যাক্টর আমার অলরেডি জানা!
Factor[] = { }

step-1: SF[N] = 2 ; Add 2 to the list ; N = N/2 = 30
step-2: SF[N] = 2 ; Add 2 to the list ; N = N/2 = 15
step-3: SF[N] = 3 ; Add 3 to the list ; N = N/3 = 5
step-4: SF[N] = 5 ; Add 5 to the list ; N = N/5 = 1

Jump out from the loop!!!

Now, Factor[] = { 2 , 2 , 3 , 5 }

এখন, একটা সংখ্যার সর্বোচ্চ কয়টা প্রাইম ফ্যাক্টর থাকতে পারে? log(N) টা! তার মানে এক্সেক্ট log(N) বার লুপ ঘুরিয়ে আমার প্রাইম ফ্যাক্টোরাইজেশন এর কাজ শেষ! কারণ, ক্ষুদ্রতম প্রাইম ফ্যাক্টর আমি সকল সংখ্যার জন্য একবারেই জেনারেট করে ফেলবো। 

Comments

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

Magic In Grid

At Coder Educational DP-B | DP Series(Episode-2)