SPOJ DIV-Divisors

প্রবলেম বর্ননাঃ এই প্রবলেম এ বলা আছে N এর জন্য 1 থেকে N পর্যন্ত যতগুলো ডিভিসর আছে সেগুলো কাউন্ট রির্টান করবে। মানে 1 থেকে 10, 00000 পর্যন্ত কাউন্ট করবে যাদের মান d(N)=(p*q)













এবার মেইন ফাংশনে আসি, ‍sieve() ফাংশনের মাধ্যমে প্রথমে পুরো প্রাইম এর জেনারেট করি এবং ফর ‍লুপ এর মাধ্যামে 1 থেকে MX পর্যন্ত অপারেশন চালাব।

প্রতিটা divisor[i] তম ডিভিসর বের করে X মধ্যে রাখব । [ উপরোক্ত প্রবলেম এ আমাদের একটা শর্ত দেওয়া হয়েছিল আমরা ‍ যদি ডিভিসর কে d(n)=p*q আকারে প্রকাশ করতে পারি তাহলে এটা আমরা প্রিন্ট করতে পারি।  if(prime_factor[x].size()==2)] এবং সেই X সংখ্যাটা ডিভিসর কাউন্ট যদি 2 টা হয় এবং X এর 0 তম ইনডেক্স যে প্রাইম ফ্যাক্টরটা আছে এবং 1 তম ইনডেক্স যে প্রাইম ফ্যাক্টর টা আছে ্ওই দু’টা সংখ্যা গুন করার ফলে যদি প্রাইম ফ্যাক্টর পাই তাহলে অবশ্যই আমরা p*q আকারে প্রকাশ করতে পারছি

কোডিং লিখতে পারি (prime_factor[x][0]*prime_factor[x][1]==x) । যদি এই কন্ডিশন সত্য হয় তাহলে আমরা কে প্রিন্ট করতে পারি। এবং তার সাথে আমরা cnt++ ভ্যালু বাড়িয়ে দিচ্ছি । কাউন্ট এর ভ্যালু 9 দিয়ে মড করে দিচ্ছি কারন প্রবলেম আমাদের 9 ঘর প্রিন্ট করতে বলা হয়েছে।


সম্পূর্ন কোড:

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

typedef long long ll ;
typedef unsigned long long ull ;

const int mx = 1000000 ;
int  cnt ;
int divisor[mx+10] ;
vector <int> prime_factor[mx+10];

void sieve()
{
    for(int i=1;i<=mx;i++)
    {
        for(int j=i;j<=mx;j+=i)
                       divisor[j]++;
    }

    for(int i=2;i<=mx;i++)
    {
        if(prime_factor[i].size()==0)
        {
            for(int j=i;j<=mx;j+=i) prime_factor[j].pb(i);
        }
    }
}

int main()
{
    sieve();

    for(int i=1;i<=mx;i++)
    {
        int x = divisor[i] ;
        if(prime_factor[x].size()==2&&prime_factor[x][0]*prime_factor[x][1]==x)
        {
            cnt++;
            if(cnt%9==0) printf("%d\n",i);
        }
    }

    return 0;
}