এই অনুচ্ছেদে আমরা দেখব কীভাবে একটি সংখ্যার সর্বোচ্চ প্রাইম ফ্যাক্টর দক্ষতার সাথে বের করা যায়। ধরা যাক একটি সংখ্যা n = 1092। আমাদের এর সর্বোচ্চ প্রাইম ফ্যাক্টর বের করতে হবে। 1092-এর প্রাইম ফ্যাক্টরগুলো হলো ২, ২, ৩, ৭, ১৩। সুতরাং সর্বোচ্চ হলো ১৩। এই সমস্যাটি সমাধানের জন্য নিচের নিয়মগুলো মেনে চলতে হবে −
এখন সংখ্যাটি বিজোড় হবে। ৩ থেকে সংখ্যার বর্গমূল পর্যন্ত, যদি সংখ্যাটি বর্তমান মান দ্বারা বিভাজ্য হয়, তবে ফ্যাক্টরটি সর্বোচ্চ হিসেবে স্টোর করুন এবং সংখ্যাকে বর্তমান সংখ্যা দিয়ে ভাগ করে দিন।
অবশেষে যদি সংখ্যা ২ থেকে বড় হয়, তবে সেটিই সর্বোচ্চ প্রাইম ফ্যাক্টর।
যখন সংখ্যাটি ২ দ্বারা বিভাজ্য, তখন ২ কে সর্বোচ্চ হিসেবে স্টোর করুন এবং সংখ্যাকে ২ দিয়ে বারবার ভাগ করুন।
স্পষ্ট ধারণার জন্য অ্যালগরিদমটি দেখে নেওয়া যাক।
অ্যালগরিদম
getMaxPrimeFactors(n)
begin while n is divisible by 2, do max := 2 n := n / 2 done for i := 3 to √n, increase i by 2, do while n is divisible by i, do max := i n := n / i done done if n > 2, then max := n end if end
উদাহরণ
#include#include int getMaxPrimeFactor(int n) { int i, max = -1; while(n % 2 == 0) { max = 2; n = n/2; //reduce n by dividing this by 2 } for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers while(n % i == 0) { max = i; n = n/i; } } if(n > 2) { max = n; } return max; } main() { int n; printf("Enter a number: "); scanf("%d", &n); printf("Max prime factor: %d", getMaxPrimeFactor(n)); }
আউটপুট
Enter a number: 24024 Max prime factor: 13
