অয়লারের টশিয়েন্ট ফাংশন

প্রথমেই আমরা Relatively Prime বা Co-Prime কথাটির সাথে পরিচিত হই । ধরি, n একটি সংখ্যা । তাহলে কোন একটি সংখ্যাকে n এর Relatively Prime/Co-Prime বলা হবে যদি ঐ সংখ্যাটি এবং n এর Greatest Common Divisor (GCD)  1 হয় ।

Euler Phi বা Euler Totient Function :

    যদি n একটি positive integer হয় তাহলে Totient Function / Phi Function , n থেকে ছোট বা n এর সমান যেসব Positive integer n এর সাথে Relatively Prime বা n এর Co-Prime সেই সংখ্যাগুলোকে efficient way তে গণনা করে দেয়। যদি আমরা n এর Co-Prime বের করতে চাই তাহলে একে Represent করা হয় Φ(n) দিয়ে ।

অর্থাৎ  Φ(n)  = Totient(n)

                        = (Number of integers <= n Co-Prime to n)

 যেমন , Φ(10) = 4 (1,3,7,9 are Co-Prime to 10)

আবার, P যদি একটি Prime number হয় তাহলে Φ(P) = P-1

Euler এর Product Formula থেকে আমরা পাই , Φ(N) = N * Π_PF ( 1 - 1/PF )

এখানে PF হল N এর Prime Factor এবং Π_PF হল সেইসব Prime Number যারা N কে নিঃশেষে ভাগ করতে পারে।

এই ফরমুলার মাধ্যমে একটি নাম্বার এর Prime Factor গুলোকে কাজে লাগিয়ে সেই নাম্বারের সাথে তার থেকে ছোট বা সমান যেসব positive integer , Relatively prime  তাদের গণনা করা হয়েছে । লিখতে পারি

আমরা 18 = 2 * 3² লিখতে পারি ।

তাহলে, Φ(18) = 18 * (1 - 1/2) * (1 - 1/3)

                     = 18 * (1/2) * (2/3)

                     = 6

 কোড ইমপ্লিমেন্টেশন ঃ



কোড বিশ্লেষণ ঃ

      আমরা জানি , সকল Number কেই Prime Number এর গুনফল আকারে লিখা যায় । Phi Function এ সেই আইডিয়াকেই কাজে লাগানো হয়েছে । আমরা এখন Φ(18) এর মান বের করবো । প্রাথমিকভাবে আমরা ধরে নেবো Φ(18) = 18 । এখন প্রাইম নাম্বার 2, 18 এর একটি Divisor । তাহলে 18 পর্যন্ত 2 এর Multiple গুলোর সাথে 18 এর GCD অবশ্যই 1 হবেনা যেহেতু 2, 18 এর একটি Divisor । 

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

অর্থাৎ আমরা দেখতে পাচ্ছি যে 18টি নাম্বারের মধ্যে exactly 18/2 = 9 টি নাম্বার 18 এর সাথে Relatively Prime না । তাহলে এই সংখ্যাগুলো আমাদের Count থেকে বাদ যাবে । বাকি থাকে 9 টি নাম্বার (1, 3, 5, 7, 9, 11, 13, 15, 17)। 2 এর পর next 3 , 18 এর একটি Prime Factor । এক্ষেত্রে যে নাম্বারগুলো আছে তাদের মধ্যে 3 এর Multiple গুলোর সাথে 18 এর GCD অবশ্যই 1 হবেনা ।

1, 3, 5, 7, 9, 11, 13, 15, 17

তাই এই 9 টি নাম্বারের মধ্যে exactly 9/3 = 3 টি নাম্বার 18 এর সাথে Relatively Prime না । এক্ষেত্রে এই 3 টি নাম্বারও আমাদের Count থেকে বাদ যাবে । 

সুতরাং Φ(18) = 6 (1, 5, 7, 11, 13, 17)

এই প্রক্রিয়াটি Number টির Square Root পর্যন্ত Loop চালিয়ে check করলেই হয় যেহেতু একটি Number এর Divisor বের করার জন্য Number টির Square Root পর্যন্ত check করলেই তার সব Divisor পাওয়া যায় ।

যখন আমাদের বার বার Phi Function call করা লাগবে তখন আমরা প্রোগ্রামটি আরো Optimize করে লিখতে পারি । অর্থাৎ Concept উপরেরটাই শুধু তার সাথে একটি কাজ করলেই হবে , যখনি আমরা কোনো Prime Number পাবো তখনি তার Phi এর মান Update করে দিবো ।

অপটিমাইজড কোড ঃ




সমাধানের জন্য সমস্যা ঃ
    #GCD Extreme (II)

রেফারেন্স ঃ
    # ProgKriya

হ্যাপি কোডিং