Almost Prime Numbers

                                        == Almost Prime Number ==

Almost Prime Number হচ্ছে সেই সকল প্রাইম নাম্বার যাদের প্রাইম ফেক্টোরিজেশন কেবলেই একটা প্রাইম নাম্বার ।
যেমনঃ
              ১-১০ পর্যন্ত Almost Prime Number ৩ টি ।
                ৪=২*২ ; ৮=২*২*২ ; ৯=৩*৩ ;
এখানে ৪,৮,৯ প্রতিটি সংখ্যার প্রাইম ফেক্টোরিজেশন কেবল একটা সংখ্যা । ৪ ও ৮ এর ক্ষেত্রে ২ এবং ৯ এর ক্ষেত্রে ৩ ।
আবার ১১-২০ পর্যন্ত Almost Prime Number ১ টি । তা হল ১৬=২*২*২*২ ; 
কিন্তু লক্ষ্য করুন, Almost Prime Number গুলুর একটি সংখ্যাও প্রাইম নাম্বার নয় । তো, সে ক্ষেত্রে আপনি যদি প্রতিটি প্রাইম নাম্বারের ২ থেকে ইনফিনিটি সংখ্যক পাওয়ারের কথা চিন্তা করেন দেখবেন আপনি আপনার Almost Prime Number গুলু পেয়ে গেছেন ।

২	৩	৫	৭	১১	১৩	১৭	১৯

ধরুন, আমার কাছে ১-২০ পর্যন্ত এই প্রাইম নাম্বার গুলু আছে ।এখন আমি প্রতিটি প্রাইমের যদি পাওয়ারের কথা চিন্তা করি (পাওয়ার > ১ ) ২০ এর আগ পর্যন্ত তাহলে কি আসে একবার দেখা যাকঃ
২ এর ক্ষেত্রে আমরা পাব - ৪(২*২); ৮(২*২*২); ১৬(২*২*২*২); ৩২(২*২*২*২*২) > ২০ 
৩ এর ক্ষেত্রে আমরা পাব - ৯(৩*৩) ; ২৭(৩*৩*৩) > ২০ 
৫ এর ক্ষেত্রে আমরা পাব - ২৫(৫*৫) > ২০... ... 
তো, ১-২০ পর্যন্ত আমরা Almost Prime পাব ( ৪,৮,৯ ও ১৬ ) মোট ৪ টি । 

এবার একটু নিচের কোডটি দেখা যাকঃ 

for(i=0;i<MX;i++)
    {
        if(!flag[i])
        {
            //for(j=p[i]*p[i];j<MX;j*=p[i]) almost.pb(j);

            for(j=i*i;j<1000000000005;j*=i)  // **** Take Care about that range ! i have got so much WA for that..
            {
                almost.pb(j);
            }
        }
    }

Where MX=1000005;  flag[0]=flag[1]=true;

আমরা আসলে পাওয়ারের কথা খাতা কলমে চিন্তা করে খুব সহজেই একটা রেইঞ্জের Almost Prime Number গুলু বের করে ফেলতে পারি কিংবা বলতে পারি ওই রেইঞ্জে কতগুলু Almost Prime Number আছে ।

কিন্তু কোডিংয়ে বিষয়টা একটু অন্য ভাবে চিন্তা করতে হবে । কেননা TLE এড়ানোর জন্য আমরা সবসময় ট্রাই করি পাওয়ার নিয়ে কাজ কম করার, তবে তা যদি কেবল ছোট রেইঞ্জের হয় তাহলে ঠিক আছে ... কিন্তু লিমিট টা যদি দশের পরে ১১ বা ১২ টা শূন্যের বোঝা মাথায় চেপে দেওয়া হয় তাহলে অগত্যা এই পাওয়ার নিয়ে আমাদের আর কিছুই করার নেই । 
তাই আমরা উপরের কোডটিতে প্রতিটি প্রাইম নাম্বারের জন্য তাঁর কাঙ্ক্ষিত লিমিট পর্যন্ত কেবল একটা আরেকটার সাথে গুণ করে গেছি এবং স্টোর করেছি ।। 

কোডটা অনেক সোজা, তাই আশা করি কার প্রবলেম হবে না ।।

তো, এভাবেই আমরা কোন প্রবলেম ছাড়াই খুব সহজেই Almost Prime Number গুলু বের করে ফেলতে পারি ।। তবে আবার বলছি ... Almost Prime Number গুলু কিন্তু একটাও Prime Number না । বরং Prime Number গুলু থেকেই এদের উৎপত্তি ।।

..................... এবার https://uva.onlinejudge.org/external/105/10539.pdf এই প্রবলেম টি আশা করি করে ফেলতে পারবেন ।। 

তারপরও যদি না পারেন এই লিঙ্কে http://psshidhu.blogspot.com/2015/10/uva-10539-almost-prime-numbers.html গিয়ে হেল্প নিতে পারেন ।। তবে কখনও কোড কপি-পেস্ট করবেন না । আগে নিজে ট্রাই করে পরে হেল্প নিবেন ।।
সব শেষে অনেক শুভ কামনা রইল । । । । 
 .................................................................. Happy Coding .....................