খুব সাধারন একটা প্রোগ্রামিং প্রবলেম- 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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// correctly worked in perfect square number –code01 | |
| #include<stdio.h> | |
| #include<time.h> | |
| int main() | |
| { | |
| int count,num,divisor; | |
| int i,j; | |
| double start=clock(); // to find out the execution time of the program | |
| scanf("%d",&num); | |
| count=2; // including 1 and num | |
| for(i=2;i<=num/2;i++){ | |
| if(num%i==0){ | |
| printf("%d ",i); | |
| count++; | |
| } | |
| } | |
| printf("\n\n\n The number of Divisors Of the Number is : %d\n",count); | |
| printf ( "\n\n Execution time : %f\n\n", ( (double)clock() - start ) / CLOCKS_PER_SEC ); | |
| return 0; | |
| } |
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।
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // correctly worked at perfect square number – code02 | |
| #include<stdio.h> | |
| #include<math.h> | |
| int main() | |
| { | |
| int i,n,limit,div=0; | |
| printf("Enter the number : "); | |
| scanf("%d",&n); | |
| limit=sqrt(n); | |
| for(i=1;i<=limit;i++) | |
| if(n%i==0){ | |
| if(i!=n/i) | |
| div=div+2; | |
| else | |
| div++; | |
| } | |
| printf("%d\n",div); | |
| return 0; | |
| } |
Practice
Problem : uva – 294 , projecteuler-
problem-12
Author : Md. Shohanur Rahaman
Date : 01/01/2015
