গসাগু-লসাগু (GCD - LCM)

গসাগুঃ 
দুইটি সংখ্যার কমন ডিভাইজরগুলোর মধ্যে সবচেয়ে বড় ডিভাইজরটিই হল ঐ দুইটি সংখ্যার  গসাগু বা Greatest Common Divisor (GCD) .

ধরা যাক,  ১২ এবং ১৮ এর গসাগু বের করবোঃ 

 12/1 = 12                       18/1 = 18  
 12/2 = 6                        18/2 = 9  
 12/3 = 4                        18/3 = 6       

১২ এবং ১৮ এর ডিভাইজরগুলো যথাক্রমে  ১,২,৩,৪,৬,১২ এবং ১,২,৩,৬,৯,১৮ এদের মধ্যে কমন ডিভাইজরগুলো হল, ১,২,৩,৬ । আর কমন ডিভাইজরগুলোর মধ্যে সবচেয়ে বড় হল ৬। সুতরাং ১২ এবং ১৮ এর লসাগু হল ৬।

GCD বের করার জন্য ছোটকালে আমরা একটি অ্যালগরিদম ব্যাবহার করেছি। ওটা আসলে ইউক্লিড অ্যালগরিদম। ধরা যাক দুইটা সংখ্যা x এবং y যেখানে x>y এদের GCD বের করতে হবে । তাহলে x কে y দ্বারা ভাগ করবো। যদি ভাগশেষ থাকে তাহলে সেই ভাগশেষ দিয়ে আবার x কে ভাগ করবো। এভাবে চলতে থাকবে যতক্ষন পর্যন্ত ভাগশেষ শুন্য না হয়। যখন ভাগশেষ শুন্য হয় এবং সে অবস্থায় যা ভাজক হিসেবে থাকে তাই গসাগু।

Algorithm

 1. Divide a by b where a>b   
 2. if reminder!=0 then then divide a by reminder  
 3. goto step 2 while untill reminder is zero  

১২ এবং ১৮ এর গসাগু এ পদ্ধতিতে করতে গেলে এমন হবেঃ 

 12| 18 |1  
   | 12 |  
   --------  
     6| 12 |2  
      | 12 |  
     ---------  
        0  

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

লসাগুঃ লসাগু বা LCM হল Least Common Multiple । দুইটা সংখ্যর কমন গুনিতকের মধ্যে সবচেয়ে ছোটটি হল লসাগু বা LCM। যেমন ২ এবং ৩ এর লসাগু বের করবো । সেক্ষেত্রে প্রথমে এদের গুনিতকগুলো বের করতে হবে- 
২ এর গুনিতকগুলো হলঃ ২,৪,৬,৮,১০,১২,১৪,১৬,১৮,২০
৩ এর গুনিতকগুলো হলঃ ৩,৬,৯,১২,১৫,১৮,২১,২৪,২৭ ,৩০

এদের মধ্যে কমন গুনিতকগুলো হলঃ ৬, ১২ ,১৮
এদের মধ্যে ছোটটি হল ৬ সুতরাং ২ এবং ৩ এর লসাগু ৬।
গসাগুর সাথে লসাগুর একটি সম্পর্ক আছে। দুইটা সংখ্যা যদি x,y হয় তাহলে

LCM(x,y) = |x * y|/GCD(x,y)
GCD LCM এর সম্পূর্ণ কোড পাওয়া যাবে এখানে 
প্র্যাক্টিস প্রব্লেমঃ UVA 11417, UVA 11388

নেগেটিভ ফ্যাক্টোরিয়াল

নেগেটিভ ফ্যাক্টোরিয়াল কি আসলেই সম্ভব?  দেখা যাক সম্ভব কিনা :P  
আমরা জানি যে,
                      N! = (N-1) X (N-2) X (N-3) X....... N
                       5!  =  1 x 2 x 3 x 4 x 5
                             = 1 x 2 x 3 x 4 x 5 x 6/6
                             = 6!/6
                             = (5+1)!/(5+1)                          
তার মানে নিঃস্বন্দেহে এইটা বলা যায় যে, N! = (N+1)!/(N+1)। সেক্ষেত্রে,
5! = 6!/6 = 120
4! = 5!//5 = 24
3! = 4!/4 = 6
2! = 3!/3 = 2
1! = 2!/2 = 1
0! = 1!/1 = 1

একইভাবে-
-1! = 0!/0 =  +∞ [(-1)! = 0!/0 = undefined]
-2! = (-1)!/-1  = -∞ 
-3! = (-2)!/-2  = +∞
-4  = (-3)!/-3 = -∞
...............................
(-N)! = (-N+1)!/(-N+1)

দেখা  যাচ্ছে যে, যখন N জোড় হয় তখন -N! = -∞ হয় আর যখন বিজোড় হয় তখন -N! =  +∞ হয়। 
প্র্যাক্টিস প্রব্লেমঃ UVA10323  

                            

প্রাইম নাম্বার- সিভ অব এরাটস্থেনিজ

সিভ মানে হল ছাঁকনি। এই এলগোরিদমে কম্পোজিট নাম্বারগুলো থেকে প্রাইম নাম্বারগুলোকে ছেঁকে আলাদা করা হয়। আর গ্রিক গণিতবিদ এরাটস্থেনিজ (২৭৬ পূর্বাব্দ – ১৯৫ পূর্বাব্দ) এই এলগোরিদমের আবিষ্কারক বিধায় এলগোরিদমটির নাম দেওয়া হয়েছে সিভ অফ এরাটস্থেনিজ। দ্রুততার সাথে প্রাইম নাম্বার বের করার ক্ষেত্রে এলগোরিদমটি এতোটাই কার্যকর যে ২২০০ বছরের পুরোনো এই এলগোরিদম আজও কম্পিউটার বিজ্ঞানে ব্যবহার করা হয়। 

ছবিঃ উইকিপিডিয়া

সিভ দুইটি জিনিসের উপর ভিত্তি করে কাজ করেঃ 

১। যে যেকোন কম্পোজিট নাম্বার দুই বা ততোধিক প্রাইম নাম্বারের গুনফলের সমিষ্টি। যেমন, ৩৫ = ৩x৫ , ২১ = ৩x৭ ।  তার মানে হল সংখ্যাটি যদি n হয় তাহলে n  = p1 X p2 X p3....pk ।

২। আমরা জানি জানি, যেকোন কম্পোজিট সংখ্যা তার বর্গমূলের সমান বা ছোট অন্তত একটি সংখ্যা দিয়ে ভাগ যাবে। 

মনে কর, তোমার কাছে ১০০ টা বক্স আছে।  তোমাকে ১০০ পর্যন্ত প্রাইম নাম্বার বের করতে হবে। তুমি প্রত্যেকটা বক্সকে ০ থেকে ১০০ পর্যন্ত নাম্বারিং করলে। এখন তোমাকে শুধু নির্দেশ করতেই পারলেই হল যে কত নাম্বারের বক্সটি প্রাইম। সেক্ষেত্রে কি করবে? হুম; একটু ভাবো! আশাকরি তোমার ভাবা শেষ। নির্দেশ করার জন্য আমরা বক্সে কিছু  জিনিস রাখবো। সেটা যেকোন কিছু হতে পারে। আমরা ০ আর ১ ব্যাবহার করবো।  যদি সংখ্যাটি প্রাইম হয় তাহলে বক্সে ১ রাখবো আর যদি প্রাইম না হয় তাহলে বক্সে ০ রাখবো। প্রথমেই মনে কর, সবগুলো বক্স প্রাইম । তাহলে আমরা সবগুলো বক্সে ১ রাখলাম । বক্স হিসেবে আমরা int টাইপের একটা অ্যারে ১০১ সাইজের অ্যারে  নিলাম। 

 prime[101]  

এখানে ০ থেকে ১০০ পর্যন্ত prime নামের ১০০ টি বক্স তৈরী হয়ে গেছে। বক্সগুলো হল... 

 prime[0],prime[1], prime[2], prime[3]........prime[100]  ইত্যাদি

ইন্ডেক্সগুলো বক্সের নাম্বার হিসেবে কাজ করবে ভেরিয়েবলের ভেতরে আমরা ০/১ রাখবো। এখন মনে করি সবগুলো নাম্বার প্রাইম। তাহলে আমরা সবগুলো বক্সে ১ রাখবো।

 for(i= 0;i<=100;i++)  
   prime[i] = 1;  

এখন আমরা আস্তে আস্তে কম্পোজিট নাম্বারগুলো আইডেন্টিফাই করবো। আমরা আগে থেকেই জানি ০ এবং ১ প্রাইম নাম্বার না। তাহলে ০ এবং ১ এর যায়গায় ০ বসিয়ে দিতে পারি। 

 prime[0] = prime[1] = 0  

এবার আমরা জানি যে ২ ব্যাতিত বাকি সব জোড় সংখ্যাই কম্পোজিট নাম্বার। তাহলে নির্দ্বিধায় ২ ছাড়া বাকি জোড় সংখ্যাগুলোকে কম্পোজিট হিসেবে আইডেন্টিফাই করতে পারি। মানে, ওগুলোতেও শুন্য বসিয়ে দেবো।

 for(i= 4;i<=100;i= i+2)  
   prime[i] = 0;  

এইবার হল বাকি নাম্বারগুলোর ফালা। আমাদের এখন শুধু আইডেন্টিফাই করতে হবে বিজোড় কম্পোজিট সংখ্যাগুলোকে। আমরা আগে থেকেই জানি যেকোন কম্পোজিট সংখ্যা দুই বা ততোধিক প্রাইম নাম্বারের গুনফল! তাহলে প্রাইম নাম্বারের গুনফলগুলোও কম্পোজিট নাম্বার। এখন সেই কাজটাই করবো।

 for(i= 3;i<=sqrt(100);i++)  
 {  
    if(prime[i] == 1)  
    for(j= i*i;j<=100;j= j+i)  
 {  
   prime[j] = 0;  
 }  
 }  

কোডটি দেখলেই বুঝে ফেলার কথা কিভাবে কাজ করছে। প্রথমে ৩ কে প্রাইম ফেলো । তারপর ৩ সহ অন্যান্য যেসব প্রাইম  এর যে গুনফল আছে সেগুলোতে ০ বসিয়ে দিবে । ৯,১২,১৫,১৮... এভাবে সে সকল কম্পোজিট নাম্বার আইডেন্টিফাই করে ফেলবে। এখন যেসব সংখ্যা কম্পোজিট সেসব ঘরে ০ আছে বাকি বাকি ঘরগুলোতে ১ আছে। যেগুলোতে ১ আছে ওগুলোই কম্পোজিট নাম্বার।
এখন সম্পূর্ণ কোডটি লিখে ফেলিঃ

 #include <stdio.h>  
 #include <math.h>  
 int main(){  
  int prime[101],i,j,n;  

  for(i= 0;i<=100;i++)  
  prime[i]= 1;  

  prime[0]= prime[1]= 0 ;  

  for(i= 4;i<=100;i= i+2)  
  prime[i]= 0;  

  for(i= 3;i<=sqrt(100);i= i+2){  
   if(prime[i]==1){  
     for(j= i*i;j<=100;j= j+i){  
       prime[j]= 0;  
     }  
   }  
  }  

  for(i= 0;i<=100;i++){  
   if(prime[i]==1)  
     printf("%d ",i);  
  }  
 return 0;  
 }  

প্রাইম নাম্বার বেসিক

প্রাইম নাম্বার বা মৌলিক সংখ্যা হল সেসব সংখ্যা যাদেরকে ১ এবং ঐ সংখ্যা ব্যাতিত অন্য কোন সংখ্যা দিয়ে নিঃশেষে ভাগ করা যায়না। অন্যভাবে বলতে গেলে , যেসব সংখ্যার মাত্র দুইটির বেশী ফ্যাক্টর/ভাজক থাকেনা তাদেরকে মৌলিক সংখ্যা বা প্রাইম নাম্বার বলে।
যেমন,  ৫ একটি প্রাইম নাম্বার কারন একে ১ এবং ৫ ব্যাতিত অন্য কোন সংখ্যা দিয়ে নিঃশেষে ভাগ করা যাবেনা। আবার এর ফ্যাক্টর  হল মাত্র দুটি (১,৫)। এরকম প্রাইম নাম্বারগুলো হল ২্‌,৩,৫,৭..
আবার যেসব সংখ্যা প্রাইম নাম্বার না তাদেরকে কম্পোজিট নাম্বার বলে। যেমন, ১০।  একে ১,২,৫,১০ ইত্যাদি দিয়ে ভাগ করা যায়।

প্রাইম নাম্বার চেকিংঃ
কোন নাম্বার প্রাইম নাম্বার কিনা তা চেক করতে সংজ্ঞাটি ব্যাবহার করা যেতে পারে। এইটা আমরা দুই ভাবে করতে পারি

১। ডিভাইজর হিসেব করেঃ আমরা জানি প্রাইম নাম্বারের ডিভাইজর ২ টার বেশী থাকেনা। তাহলে আমরা ১ থেকে শুরু করে ঐ সংখ্যা পর্যন্ত ভাগ করে দেখতে পারি। যদি ডিভাইজর দুইটার বেশী না হয় তাহলে সংখ্যাটি প্রাইম আর যদি বেশী হয় তাহলে সংখ্যাটি প্রাইম না। আচ্ছা, আমরা ঐ সংখ্যা পর্যন্ত ভাগ করছি কেন ? কারন সংখ্যাকে তার চেয়ে বড় সংখ্যা দ্বারা ভাগ করা যাবেনা। ৮ কে নিশ্চয়ই ৯ দ্বারা ভাগ যাবেনা তাইনা?

২। ১ বা ঐ সংখ্যা বাদে অন্য কোন সংখ্যা দিয়ে ভাগ করা যায় কিনা তা দেখেঃ এক্ষেত্রে আমরা ২ থেকে শুরু করে ঐ সংখ্যার আগের সংখ্যা পর্যন্ত ভাগ করে দেখতে পারি যদি ভাগ না যায় তাহলে সংখ্যাটি প্রাইম আর নাহলে প্রাইম না । সংখ্যাটি যদি ৮ হয় তাহলে আমরা ২ থেকে শূরু করে ৭ পর্যন্ত ভাগ করবো । প্রথমে নিজে কোড করতে চেষ্টা কর তারপর কোড দেখো ।

প্রথম পদ্ধতিঃ

 #include <stdio.h>  
 int main()  
 {  
   int n,i, count= 0;  
   scanf("%d", &n);  
   for(i= 1;i<= n;i++)  
   {  
     if(n%i == 0)  
       count++;  
   }  
   if(count == 2)  
     printf("Prime\n");  
   else  
     printf("Not prime\n");  
  return 0;  
 }  

দ্বিতীয় পদ্ধতিঃ

 #include <stdio.h>  
 int main()  
 {  
   int n,i, flag= 1;  
   scanf("%d", &n);  
   for(i= 2;i<n;i++)  
   {  
     if(n%i == 0)  
       {  
         flag= 0;  
         break;  
       }  
   }  
   if(flag == 1)  
     printf("Prime\n");  
   else  
     printf("Not prime\n");  
  return 0;  
 }  

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

 #include <stdio.h>  
 int main()  
 {  
   int n,i, flag= 1;  
   scanf("%d", &n);  
   for(i= 2;i<=n/2;i++)  
   {  
     if(n%i == 0)  
       {  
         flag= 0;  
         break;  
       }  
   }  
   if(flag == 1)  
     printf("Prime\n");  
   else  
     printf("Not prime\n");  
  return 0;  
 }  

সবই ঠিক রাখলাম শুধু n/2 পর্যন্ত ভাগ করলাম। এখন কথা হল এটাই কি পর্যাপ্ত ? N এর মান যদি ১০^২৫ বা তার উপরে হয়  তাহলে রেজাল্ট আসতে দিন লেগে যাবে। আর আমাদের প্রোগ্রামিং করাটাই বৃথা হয়ে যাবে।  প্রোগ্রামিং করার একটা কারন হল সময় বাঁচানো উলটো যদি সময়ের অপচয় হয় তাহলে প্রোগ্রামিং করে লাভ কি ? তখন সারাদিন এর পেছনে বসে থাকবে আর বলবে Programmer has no life. লাইফ তো মিয়া নিজেই ধ্বংশ করলা।

যাইহোক কাজের কথায় আসি, এর চেয়ে আরো  এফিসিয়েন্ট ওয়েতে আমরা করতে পারি। আমাদের আসলে n/2 পর্যন্ত ভাগ করার মোটেও প্রয়োজন নেই। কারন যেকোন সংখ্যার স্কয়ার রুট পর্যন্ত ভাগ করলে আমরা সকল ডিভাইজর পেয়ে যাই; তাহলে ডিভাইজর পাওয়ার জন্য n/2 পর্যন্ত ভাগ করার কি দরকার?
ধরা যাক একটি সংখ্যা ৬৪, এর ফ্যাক্টরগুলো বের করিঃ
৬৪/১ = ৬৪
৬৪/২ = ৩২
৬৪/৪= ১৬

উপর থেকে দেখা যাচ্ছে যে ৬৪ এর ফ্যাক্টরগুলো হল ১,২,৪,১৬,৩২,৩৬ । এই ফ্যাক্টরগুলো আমরা কিভাবে পেলাম? ১ থেকে ৪ সংখ্যা দিয়ে পর্যন্ত ভাগ করে। আর ৬৪ এর স্কয়ার  রুট হল ৪।

৬৪ কে ২ দিয়ে ভাগ হওয়া মানে ৩২ দিয়েও ভাগ হবে আবার ৪ দিয়ে ভাগ হওয়া মানে ১৬ দিয়ে ভাগ হবে। তাহলে ৩২ এবং ১৬ দিয়ে ভাগ করা আমরা সহজেই ইগ্নোর করতেই পারি। তাহলে আমরা ২ থেকে শুরু করে স্কয়ার রুট অব n পর্যন্ত ভাগ করলেই আমরা বের করতে পারি সংখ্যাটি প্রাইম কি প্রাইম না । কোডটি করে ফেলিঃ

 #include <stdio.h>  
 #include <math.h>  
 int main()  
 {  
   int n,i, flag= 1;  
   scanf("%d", &n);  
   for(i= 2;i<=sqrt(n);i++)  
   {  
     if(n%i == 0)  
       {  
         flag= 0;  
         break;  
       }  
   }  
   if(flag == 1)  
     printf("Prime\n");  
   else  
     printf("Not prime\n");  
  return 0;  
 }  

এখন আমাদের টাইম sqrt(n) পর্যন্ত নেমে আসছে। যেটা ৫০০০০ এর যায়গায় হয়ে গেছে sqrt(১০০০০০)  যা ৩১৬ মিলিসেকেন্ড। আজ এ পর্যন্তই, দেখা হবে অন্য কোন সময়ে। 

UVA 884-Factorial Factor

প্রব্লেমঃ যেকোন কম্পোজিট নাম্বারকে এক বা একাধিক প্রাইম নাম্বারের গুনফল আকারে প্রকাশ করা যায় । যেমন
৪= ২*২ (২ টি প্রাইম)
৬= ২*৩  (২ টি প্রাইম)
৮= ২*২*২ (৩ টি প্রাইম)
একটি নাম্বার দেওয়া থাকবে সে নাম্বারের ফ্যাক্টোরিয়ালের এরকম মোট কতটি প্রাইম দ্বারা প্রকাশ করা যেতে পারে তা বের করতে হবে।
যেমন, ৮! = ১*২*৩*৪*৫*৬*৭*৮
               = ১*২*৩*২*২*৫*২*৩*২*২*২ (১১ টি)

প্রব্লেম হিন্টঃ প্রথমে প্রতিটি নাম্বারের প্রাইম ফ্যাক্টর বের করতে হবে। সর্বোচ্চ ভেলু যেহেতু ১০০০০০০  তাই সেক্ষেত্রে ভুলেও সাধারনভাবে ফ্যাক্টর বের করা যাবেনা। তারপর ফ্যাক্টোরিয়াল মানগুলো যোগ করা ওই পজিশনে বসিয়ে রাখতে হবে এবং প্রিন্ট করে দিলেই কাজ শেষ।

কোডঃ

 #include <bits/stdc++.h>  
 #include <cstdio>  
 #define MAX 1000001  
 using namespace std;  
 int factors[MAX];  
 int factorialcount[MAX];  
 int x, temp;  


 int primeFactor(int x)  
 {  
   int count = 0;  
   int i,j;  
     for(j=2;j*j<=x;j++)  
     {  
       if(x%j == 0)  
       {  
         count++;  
         x= x/j;  
         j= 1;  
       }  
     }  
     if(x>1)  
       count++;  
   return count;  
   }  


 int main()  
 {  
   int n, i, sum;  
   factors[1] = 0;  
 for(i= 2;i<MAX;i++)  
   factorialcount[i] = factorialcount[i-1]+ primeFactor(i);  

   while(scanf("%d", &n)!= EOF)  
   {  
     printf("%d\n",factorialcount[n]);  
   }  
   return 0;  
 }