খুব সাধারন একটা প্রোগ্রামিং প্রবলেম- n একটি integer এর Total Divisor সংখ্যা বের করতে হবে, সহজ কথায় যে সকল সংখ্যা দিয়ে n কে ভাগ করলে ভাগফল শূন্য থাকে সে সকল সংখ্যাই হচ্ছে n এর divisor।
এখন 1 থেকে n-1 পর্যন্ত লুপ চালালেই আমরা বের করতে পারবো n এর divisor গুলো।
for(i=1;i<n;i++){
if(n%i==0)
printf(“Divisor : %d ”,i);
}
সহজ হিসাব কিন্তু n এর value যদি অনেক বড় হয় ধরা যাক n=1000000 তাহলে কি হবে আমার লুপ চলবে 999999 পর্যন্ত, তার মানে প্রোগ্রামের Run Time অনেক বেড়ে যাবে।
কিন্তু আমরা যদি চাই তাহলে প্রোগ্রামটি আরও efficient করতে পারি।
n এর divisor বের করার জন্য n-1 পর্যন্ত ভাগ করে দেখার প্রয়োজন নাই আমরা n/2 পর্যন্ত ভাগ করেই n এর divisors গুলো বের করতে পারি, n কে n/2 এর পর আর কোন সংখ্যা দিয়ে ভাগ করা যাবে না, মানে n যদি composite number হয় তাহলে একে 1 থেকে n/2 পর্যন্ত সংখ্যা দিয়েই ভাগ করা যাবে ।
যেমনঃ
n=10 , n/2=5
১ থেকে ৫ এর মধ্যে সংখ্যা আছে ১,২,৩,৪,৫।তাহলে ১০ এর divisor 2 and 5।
Total Divisor সংখ্যা = 6 (include 1 and 28)
Total Divisor সংখ্যা = 6 (include 1 and 28)
কিন্তু তারপরও প্রোগ্রাম খুব একটা efficient হয় না, আমি প্রোগ্রামটির execution time বের করে দিয়েছি একটু খেয়াল করে দেখলেই বুঝতে পারবেন।
// code
Prime Factorization এর মাধ্যমে অনেক efficient wayতে কোন নাম্বারের মোট Divisor সংখ্যা বের করা যায়।
কোন natural নাম্বারকে তার প্রাইম ফ্যাক্টর গুলোর product হিসেবে represent করা যায়।
n= xa * yb * Zc …………….
এখানে n একটি প্রাইম integer number, X,Y and Z হচ্ছে n এর প্রাইম ফ্যাক্টর এবং a,b and c হচ্ছে X,Y,Z এর exponent।
এখন n এর Divisor সংখ্যা calculate করা যায় এভাবে,
d=(a+1)*(b+1)*(c+1)*…………………..
একটা উদাহরণ দেওয়া যায় এভাবে,
n=Xa * Yb
n=2²*71
a=2, b=1
number of divisor = (a+1)*(b+1) = =(2+1)*(1+1 )= 6
অর্থাৎ 28 এর Divisor সংখ্যা 6।
আরেক ভাবে আমরা Divisor বের করতে পারি, কোন সংখ্যা n এর Divisor বের করার জন্য আমাদের n/2 পর্যন্ত ভাগ করে দেখার দরকার নাই, ওই সংখ্যার বর্গমূল (sqrt(n)) পর্যন্ত চেক করলেই হবে।
কেননা, যদি n=a×b হয় (অর্থাৎ n যদি যৌগিক সংখ্যা হয়) আর তাদের একটা ডিভিজর যদি sqrt(n) এর ছোট হয়, অন্যটা অবশ্যই sqrt(n) এর বড় হবে । সেজন্য sqrt(n) এর ছোট সবক'টা ডিভিজর এর জন্য আমরা divisor কে 1 করে না বাড়িয়ে 2 করে বাড়াতে পারি। শুধু যদি কোন ডিভিজর sqrt(n) সমান হয় তাহলে 1 যোগ হবে(এটা হয় শুধু মাত্র perfect square number এর ক্ষেত্রে)।
যেমনঃ n=28, sqrt(n)=5
5 এর থেকে ছোট 28 Divisor গুলো হল 1,2,4 যাদের প্রত্যেকটির জন্য আমরা আরেকটি Divisor পাবো যেটি কিনা sqrt(n)=5 এর চেয়ে বড়।
28%1==0 so divisor = 1 and 28
28%2==0 so divisor = 2 and 14
28%4==0 so divisor = 4 and 7
Total = 6 (notice that 28,14 and are greater than 5,that why we should increment our divisor counter +2)
36 (perfect square number)
sqrt(36)=6
36%1==0 so divisor = 1 and 36
36%2==0 so divisor = 2 and 18
36%3==0 so divisor = 3 and 12
36%4==0 so divisor = 4 and 9
36%6==0 so divisor = 6 and 36 (notice that 36 is counted previous that why we should increment the step just 1)
Total Divisor = 9।
Practice
Problem : uva – 294 , projecteuler-
problem-12
Author : Md. Shohanur Rahaman
Date : 01/01/2015
