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