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

Game Theory with examples

Game Theory with examples Introduction In this article I will be covering problems related to two players game in which it is assumed that both players play optimally and we have to find out the winner of the game. First we will look at the  basic   division of positions to winning and losing . Then we will see the  Game of Nim  and then see how it will be used to solve the  Composite games . Basic Division of positions to winning and losing Problem Statement:  Consider a simple game played by two players A and B . There are n stones on the table. Each player can pick 1 , 2 or 5 stones in each turn. Both players pick the stones alternately until the total number of stones left on the table is 0. The player unable to make the move will lose. Assuming that both the players play optimally, output the winner of the game. Solution:  As you can see positions 1 , 2 and 5 are winning positions since the player can pick up all the stones and other player will n...
Post a Comment
Read more

Breaking The Summation Formula (Part 1)

 Q. f ( n ) =  - 1 + 2 - 3 + .. + ( - 1) n n .  Given n, find out f(n) Approach(1)- Bruteforce: 1. Calculation sum=n*(n+1)/2 2. loop[i=1,i=n : i+=2] odd+=i 3.ans=sum-2*odd Code: #include < bits / stdc ++. h > using namespace std ; int main (){   long long x ; cin >> x ; long long p =( x *( x + 1 ))/ 2 ; long long bad = 0 ; for ( long long i = 1 ; i <= x ; i += 2 ) bad += i ; cout << p - 2 * bad << endl ; } Approach(2)-Greedy: Basic: s=1+2+3+4+....+n Formula: sum=n*(n+1)/2= (n/2) + (n+1).2 ...
Post a Comment
Read more

NT Part 2: Generating Primes, Prime Test, Prime Factorization

  Generating primes fast is very important in some problems. Let's cut to the chase and introduce Eratosthenes's Sieve. The main idea is the following. Suppose we want to find all primes between 2 and 50. Iterate from 2 to 50. We start with 2. Since it is not checked, it is a prime number. Now check all numbers that are multiple of    except  2. Now we move on, to number 3. It's not checked, so it is a prime number. Now check all numbers that are multiple of  ,   except  3. Now move on to 4. We see that this is checked - this is a multiple of 2! So 4 is not a prime. We continue doing this. Here's the implementation. #include <stdio.h> int primechk [ 21000 ] ;   void preprocess ( void ) { int i, j ; for ( i = 2 ; i <= 20000 ; i ++ ) { primechk [ i ] = 1 ; } for ( i = 2 ; i <= 20000 ; i ++ ) { if ( primechk [ i ] == 1 ) { for ( j = 2 ; i * j <= 20000...
Post a Comment
Read more