Skip to main content

Trial Division Algorithm


Trial Division Algorithm


সাধারণত মৌলিক সংখ্যা বলতে আমরা বুঝি ২,৩,৫,৭,১১ এ ধরণের সংখ্যাকে। কেন এগুলো মৌলিক সংখ্যা? কারণ, এসব সংখ্যা শুধু মাত্র ২ টা সংখ্যা দ্বারা বিভাজ্য। প্রথমটি হলো ১ এবং পরেরটি হলো ঐ সংখ্যা নিজেই।
উদাহরণস্বরূপ, ধরুন ৫ সংখ্যাটি মৌলিক। এর কারণ ১ থেকে ৫ এর মধ্যে ৫ সংখ্যাটি শুধু মাত্র ১ এবং ৫ দ্বারাই বিভাজ্য। আবার ৯ সংখ্যাটি ১ থেকে ৯ এর মধ্যে ১,৩ এবং ৯ দ্বারা বিভাজ্য। যেহেতু ৩ টি সংখ্যা দ্বারা ৯ বিভাজিত হচ্ছে তাই ৯ মৌলিক সংখ্যা নয়।
তাহলে আমরা বলতে পারি একটা সংখ্যা মৌলিক সংখ্যা হবার শর্ত হলো-
দুটি বিভাজক থাকতে হবে এবং বিভাজক দুইটি ১ এবং ঐ সংখ্যা নিজেই।
[বি.দ্রঃ ১ সংখ্যাটি মৌলিক সংখ্যা নয় কারণ ১ এর বিভাজক মাত্র ১টি।]
মৌলিক সংখ্যা বের করার উপায়কে তাহলে আমরা একটু কোডে লিখে ফেলি। 

int IsPrime(x) //একটা ফাংশন লিখছি যেটা ইন্টিজার টাইপ ভ্যালু রিটার্ন করবে
{
int result=1;// প্রথমে ধরে নিব x প্রাইম তাই result এ  ১ রেখেছি
for(int i=2;i<x;i++) // লুপ শুরু হবে ২ থেকে এবং যে সংখ্যা চেক করব তার আগে পর্যন্ত যাবে
        {
                if(x%i==0) 
                        result -1; //যদি  ২ থেকে (x-১) এর মধ্যে কোন সংখ্যা দিয়ে x সংখ্যাটি ভাগ যায় তাহলে সেটা আর প্রাইম থাকবে না কারণ আমরা আগেই বলেছি প্রাইম হতে হলে ১ এবং ঐ সংখ্যা দ্বারা শুধুমাত্র ভাগ যাবে। result এ -১ রাখছি
        }
        return result; // প্রাইম হলে ১ রিটার্ন করবে আর না হলে -১ রিটার্ন করবে
}

এইবার পুরো কোডটি আমরা চাইলে লিখে ফেলতে পারি।তবে সেটা আমি করে দেখাচ্ছিনা কারণ আমি আশাবাদী আপনারা সবাই বাকি কাজটা করতে পারবেন।

এবার আমরা একটু লক্ষ্য করব যে আমাদের কোড একটু অপটিমাইজ করা যায় কিনা।
তার আগে আমরা কিছু উদাহরণ দেখব এবং একটু অব্জার্ভ করব কি হচ্ছে।
ধরণের আমরা দেখতে চাই যে ৯ সংখ্যাটি প্রাইম নাম্বার কিনা।
আগের কোডের আমরা যা করেছি সেটা অনুযায়ী ৯ কে হলো ২ থেকে ৮ পর্যন্ত   সব সংখ্যা দিয়ে ভাগ করার চেষ্টা করব। ১ টা সংখ্যা দিয়ে নিঃশেষে বিভাজিত হলে সেটি আর প্রাইম নাম্বার থাকবে না।তাইত?
আচ্ছা, এবার একটু লক্ষ্য করুন।সাধারণত  ৯ যে প্রাইম নাম্বার না সেটি সিদ্ধান্ত নেওয়ার জন্য আমরা কি করছি?
প্রথমে  ৯ কে ২ দিয়ে ভাগ দিচ্ছি ভাগশেষ ১
এরপর ৯ কে ৩ দিয়ে ভাগ দিচ্ছি ভাগশেষ ০
সিদ্ধান্তঃ ৯ প্রাইম নাম্বার নয়

আমাদের কিন্তু আর চেক করার দরকার নাই কারণ যেহেতু আমরা কোডে দেখেছি এবং কারণ ব্যাখাও করেছি যে 2 থেকে (x-1) এর মধ্যে কোন সংখ্যা দিয়ে নিঃশেষে বিভাজ্য হলে সংখ্যাটি প্রাইম নয়।
এবার দেখুন, 
“কোন একটা সংখ্যা প্রাইম নাম্বার কিনা এটা চেক করার জন্য আমরা লুপ ঐ সংখ্যার অর্ধেক মান পর্যন্ত চালালেই হবে”
তাহলে পরিবর্তিত কোডটি হলো-
int IsPrime(x)
{
int result=1
for(int i=2;i<=x/2;i++)
        {
                if(x%i==0) 
                        result -1;    
}
        return result;
}
আরও অপটিমাইজেশন করতে পারি আমরা তাহলে লুপটা √x পর্যন্ত চালাই। আমি কারণ বলব না তবে হিন্ট দিতে পারি!
যেহেতু প্রতিটি সংখ্যাকে আমরা মিনিমাম দুইটা সংখ্যার গুনফল আকারে লিখতে পারি।
যেমনঃ 9= 3 x 3 ,10=5 x 2 
তাহলে সাধারণ ফর্ম C=A x B এখানে লক্ষণীয়,
A=B হলে A*A=C => A=√C
A<B হলে A<√C ,B>√C
B<A হলে B<√C ,A>√C


প্র্যাক্টিসঃ আপনাদের কাজ হলো এমনটা প্রোগ্রাম লেখা যেটা ইউজারের কাছ থেকে দুইটা ইনপুট নিবে এবং প্রথম ইনপুট নির্দেশ করবে শুরুর পয়েন্ট এবং পরের ইনপুট নির্দেশ করবে শেষের পয়েন্ট । এই দুইটি পয়েন্টের মাঝে যতগুলো মৌলিক সংখ্যা আছে সবগুলো প্রিন্ট করে দেখাতে হবে। মোট মৌলিক সংখ্যা কতটি আছে সেটিও প্রিন্ট করতে হবে।
অব্জারভেশনঃ আপনারা দুটি নিয়ম ব্যবহার করেই কোড লিখবেন এবং লক্ষ্য করবেন দুইটি কোডে টাইম কমপ্লেক্সিটি এর ডিফারেন্স কেমন। 

ধন্যবাদ আজ এই পর্যন্তই।এর পরে আমরা প্রাইম নাম্বার বের করার আরেকটি মজার এলগরিদম দেখব ইনশাআল্লাহ্‌। ধন্যবাদ সবাইকে।

Labels:

Comments

Post a Comment

Popular posts from this blog

NT Part 4: Mobius Function Part 1. The Introduction

  What is mobius function? This function is notated as  .  This function has lots of definitions. However, the main definition is the following.  is   if   or   is square-free and has even number of prime divisors.  is   if   is square-free and has odd number of prime divisors.  is   if   is not square-free.  also has a lot of interesting properties that make   so important.  for all  ,  and   is multiplicative. (A function   is multiplicative if   for all  . ) How do we calculate   fast? Again, we can tweak the Eratosthenes's Sieve a little bit. void preprocess ( void ) { int i, j ; for ( i = 1 ; i <= 111100 ; i ++ ) { mu [ i ] = 1 ; primechk [ i ] = 1 ; } primechk [ 1 ] = 0 ; for ( i = 2 ; i <= 111100 ; i ++ ) { if ( primechk [ i ] == ...
Post a Comment
Read more

NT Part 1:GCD, LCM, Euclidean Algorithm

  The definitions of GCD and LCM are well-known, (and taught in middle school I think) I will skip the definitions. Also, since  ,  calculating GCD is equivalent to calculating LCM. Now, how do we calculate the GCD of two numbers? A naive solution would be iterating over all positive integers no more than  . This will get the GCD in  ,  very very slow. We can calculate the GCD of   in   using Euclidean Algorithm. This algorithm uses the easy-to-prove fact  ,  where   is the remainder when   is divided by  ,  or just a%b. We can now use the following code. #include <iostream> using namespace std ; int gcd ( int u, int v ) { return u % v == 0 ? v : gcd ( v,u % v ) ; } int main ( void ) { int x, y ; cin >> x >> y ; cout << gcd ( x,y ) ; } How do we prove that this algorithm is  ?  Well, let's suppose that we started with  . Then...
Post a Comment
Read more

কোডফোর্সেস বেসিক প্রবলেম লিস্ট ১

IMPLEMENTATION  Problem 1: Codeforces 835A Problem 2: Codeforces 935B Problem 3: Codeforces 868A Problem 4: Codeforces 868B LOOPS (NOT NESTED) Problem 1: Codeforces 839A Problem 2: Codeforces 939A Problem 3: Codeforces 893A Problem 4: Codeforces 935A Problem 5: Codeforces 961A Problem 6: Codeforces 828A Problem 7: Codeforces 867A Problem 8: Codeforces 939B NESTED LOOPS  Problem 1: Codeforces 894A Problem 2: Codeforces 897A Problem 3: Codeforces 822B Problem 4: Codeforces 828B Problem 5: Codeforces 886A (Can also be solved using sorting) Problem 6: Codeforces 907A Problem 7: Codeforces 22B MATH Problem 1: Codeforces 869B  (Uses a loop) Problem 2: Codeforces 875A  (Uses a nested loop) Problem 3: Codeforces 922B  (Uses a nested loop)
Post a Comment
Read more