প্রাইম ডিভিজর এবং ফ্যাক্টরাইজেশন(Prime Divisors and Factorization)
সত্যিই সিভ দিয়ে আগে ইনপুট লিমিট পর্যন্ত সবগুলো নাম্বার থেকে এদের মাঝে প্রাইম নাম্বার গুলো কে যদি আগে মার্ক করে রাখতে পারি তাহলে কিন্তু আমাদের কাজ অনেক কমে যাচ্ছে। এর জন্যে প্রাইম নাম্বার গুলো আলাদা অ্যারে তে নেওয়ার ও প্রয়োজন নেই। মার্ক অ্যারেই যথেষ্ট আমাদের জন্য।
|
const int N = 1e8;
bool mark[N+1];
void sieve() { mark[0] = true; mark[1] = true; for (int i = 4;i <= N;i += 2) { mark[i] = true; } int lim = sqrt(N); for (int i = 3;i <= lim;i += 2) { if (mark[i] == false) { for (int j = i*i;j <= N;j += i+i) { mark[j] = true; } } } }
void find_prime_div(int n) { // i*i <= n will make sure that i will be // not greater then square root of n for (int i = 1;i*i <= n;i++) { if (n%i==0) { if (mark[i]==false) { // if mark[x] is false then x is prime cout << i << ' '; } if (n/i != i) { // if i is not square root of n if (mark[n/i]==false) { cout << n/i << ' '; } } } } cout << '\n'; } |
এখন যে নিয়ম টি দেখব তাকে বলা হয় প্রাইম ফ্যাক্টরাইজেশন। এটি কীভাবে কাজ করে? প্রথমে সবথেকে ছোট প্রাইম মানে 2 থেকে শুরু করব। 2 দিয়ে যতক্ষণ ভাগ যাবে ততক্ষণ ভাগ করতেই থাকব যেমন, n%2==0 then, n = n / 2; এক সময় 2 দ্বারা ভাগ করা যাবে না তখন n বিজোড় হবে। এখন, পরবর্তী প্রাইম 3 দিয়ে চেষ্টা করব। এভাবে n এর বর্গমূল পর্যন্ত চেষ্টা করব। n যদি 1 এর সমান হয়ে যায় অথবা বর্তমান প্রাইম নাম্বারটি যদি n এর বর্গমূল থেকে বড় হয়ে যায় তাহলে আমাদের কাজ শেষ। বর্তমান প্রাইম তখন ই বড় হবে যখন n এর ভ্যালু 1 বা n নিজেই প্রাইম হবে। আচ্ছা কিছু সংখ্যার জন্যে কাজ টি দেখে নেই তাহলে আরো পরিস্কার হবে।
n এর ভ্যালু যদি 12 হয়,
12 = 2 X 6
6 = 2 X 3
3 = 3 X 1
12 = 2 X 2 X 3
n এর ভ্যালু যদি 30 হয়,
30 = 2 X 15
15 = 3 X 5
5 = 5 X 1
30 = 2 X 3 X 5
n এর ভ্যালু যদি 90 হয়,
90 = 2 X 45
45 = 3 X 15
15 = 3 X 5
5 = 5 X 1
90 = 2 X 3 X 3 X 5
নিচের ছবিটি দেখলে আশাকরি আরো ভালো করে বুঝা যাবে। আর আমার মত ফাঁকিবাজ রা এটাও বুঝতে পারবে যে এটা আসলে হাই স্কুল এর সাধারণ গণিত :|
 |
| প্রাইম ফ্যাক্টরাইজেশন |
এভাবে, আমরা প্রাইম ডিভিজর গুলো পেয়ে যেতে পারি। এখন হয়ত আমার মত আপনারো প্রশ্ন আসতে পারে, এটা কীভাবে কাজ করলো? এটা কী সব নাম্বারের জন্যেই সঠিক আউটপুট দিবে? উত্তর হ্যাঁ। আর এটা কীভাবে কাজ করলো তা একটু বলার চেষ্টা করি। n যদি 2 দিয়ে ভাগ হয় তাহলে খেয়াল করলে দেখবেন n ছাড়া n এর সবথেকে বড় ডিভিজর কখনোই n/2 এর থেকে বড় হবে না। তাহলে n = n/2 নিয়ে বাকি নাম্বার গুলো বাতিল করে দিয়ে n কে ছোট করে নিতে পারি। একই ভাবে বর্তমান n যদি এখন 3 দিয়ে ভাগ করা যায় তাহলে n ছাড়া n এর সবথেকে বড় ডিভিজর n/3 এর থেকে বড় হবে না। যদি বড় থাকেও তাহলে সেটি আগের প্রাইম দিয়ে কাটা হয়ে গেছে এবং সেটি কোনভাবেই প্রাইম নয়। আমাদের দরকার প্রাইম ডিভিজর। আবার কাটা না পড়ে থাকলে তাহলে বর্তমান প্রাইমের আগের গুলো দিয়ে সেটি বিভাজ্য নয়। যেমন 65 কে যদি ধরি, তাহলে 65 কে বাদ দিলে 65 এর সবথেকে বড় ডিভিজর 13 যা 5 দিয়ে ভাগ করার ফলে হয়েছে। এবং 5 এর আগের কোন প্রাইম দিয়েই 65 বিভাজ্য নয়। ভালো করলে খেয়াল করলে দেখবেন এই কাজ গুলো সিভের আইডিয়া থেকেই এসেছে।
|
const int N = 1e8;
vector <int> p; bool mark[N+1];
void sieve() { mark[0] = true; mark[1] = true; for (int i = 4;i <= N;i += 2) { mark[i] = true; } p.push_back(2); int lim = sqrt(N); for (int i = 3;i <= lim;i += 2) { if (mark[i] == false) { p.push_back(i); for (int j = i*i;j <= N;j += i+i) { mark[j] = true; } } } }
vector <int> p_d;
void find_prime_div(int n) { for (int i = 0;i < p.size() && p[i]*p[i] <= n;i++){ // if current n is prime then stop if (mark[n]==false) break; if (n%p[i] == 0) { // current prime divides n then divide n // until current n is not divisible by // current prime and store current prime while (n%p[i] == 0) { p_d.push_back(p[i]); n /= p[i]; } } }
// if n is greater than 1 then n must be prime if (n > 1)p_d.push_back(n);
// printing all prime factor // printing all prime factor for (int i = 0;i < p_d.size();i++) { cout << p_d[i] << ' '; }cout << '\n'; } |
আমরা এইভাবে প্রাইম ফ্যাক্টরাইজ করে 10000000000000000 (1e16) পর্যন্ত নাম্বারের জন্যেও প্রাইম ডিভিজর গুলো বের করে ফেলতে পারব। তবে এই প্রোগ্রামে একটু সমস্যা আছে। 100000000 (1e8) এর উপরে গেলেই আমি মার্ক অ্যারে ব্যবহার করতে পারব না। তবে চিন্তা নেই কারণ যেহেতু আমার N এর বর্গমূল পর্যন্ত প্রাইম গুলোই শুধু লাগছে তাই মার্ক অ্যারেতে N এর বর্গমূল এর থেকে বেশি ভেরিয়েবল লাগবে না। এবার sieve(); ফাংশনের কমপ্লেক্সিটি হবে O(sqrt(N) log(log(sqrt(N))));। তবে, find_prime_div(); ফাংশন টি এবার সবথেকে খারাপ কেইস মানে ইনপুট নিজেই প্রাইম হলে কমপ্লেক্সিটি প্রায় O(sqrt(n)); কাছাকাছি চলে যাবে।
|
vector <long long> p_d;
void find_prime_div(long long n) { for (int i = 0;i < p.size() && p[i]*p[i] <= n;i++){ long long cur = p[i]; // if current prime is greater then sqrt(n) then stop if (cur*cur > n)break; if (n%cur == 0) { // current prime divides n then divide n // until current n is not divisible by // current prime and store current prime while (n%p[i] == 0) { p_d.push_back(p[i]); n /= p[i]; } } }
// if n is greater than 1 then n must be prime if (n > 1)p_d.push_back(n);
// printing all prime factor // printing all prime factor for (int i = 0;i < p_d.size();i++) { cout << p_d[i] << ' '; }cout << '\n'; } |
এই বিষয়ে আরো টিউটোরিয়াল।
টিউটোরিয়াল ১
টিউটোরিয়াল ২
টিউটোরিয়াল ৩
টিউটোরিয়াল ৪
No comments