প্রাইম নিয়ে যত কথা – ১

নাম্বার থিওরির গুরুত্বপূর্ণ একটি টপিক হল প্রাইম নাম্বার বা মৌলিক সংখ্যা। আজ প্রাইম নাম্বার বা মৌলিক সংখ্যার উপর কিছু বেসিক আলোচনা করবো আমরা। আচ্ছা তাহলে আগে জানা যাক মৌলিক সংখ্যা কি? যেসব সংখ্যাকে ওই সংখ্যা এবং ১ ছাড়া আর কোন সংখ্যা দিয়ে ভাগ করা যায়না সেগুলোই মৌলিক সংখ্যা। যেমন ঃ ২ , ৩ , ৫ ইত্যাদি। আজ আমরা দেখবো কিভাবে সহজেই আমরা একটি সংখ্যা প্রাইম কিনা তা বের করার কোড। এরপর দেখবো কিভাবে একটি সংখ্যার প্রাইম ফ্যাক্টরাইজেশন করা যায়।

আমরা যেহেতু ইতিমধ্যে জেনে গেছি যে প্রাইম কিভাবে বুঝতে হয় তাহলে আমরা বলতে পারি যে কোন সংখ্যা N প্রাইম কিনা তা জানার জন্য ২ থেকে N-১ পর্যন্ত সংখ্যা দিয়ে ভাগ করে যদি দেখি যে N কে ভাগ করা যাচ্ছেনা তাহলেই ধরে নেব সংখ্যাটি প্রাইম।

তাহলে কোডে দেখি প্রসেসটা।

আমরা একটি বুলিয়ান ভ্যারিয়াবল এ প্রথমে true নিয়ে নিচ্ছি। যদি প্রাইম চেক করার সময় দেখি যে N কোন সংখ্যা দ্বারা বিভাজ্য তাহলে তা false করে দিব। তারপর এর মানের উপর নির্ভর করে বুঝবো প্রাইম নাকি প্রাইম না। খুবই সোজা কোড।

এখন আমাদের শুধু কোড করলেই হবেনা। কোড কি Efficient কিনা তাও দেখতে হবে। খেয়াল করে দেখি আমরা প্রাইম বাদে কোন সংখ্যাকে সর্বনিম্ন দুই ভাগে ভাগ করতে পারি। জোড় সংখ্যা গুলো কে। তার মানে আমরা যে সংখ্যাই নেই না কেন তার অর্ধেক থেকে বড় সংখ্যা ( < N) ওই সংখ্যা কে ভাগ করতে পারবেনা। যেমন ঃ ধরা যাক ১০। এর অর্ধেক হল ৫। আমরা খেয়াল করলেই দেখবো ৬ ৭ ৮ ৯ এগুলো ১০ এর ভাজক না। তাহলে আমরা কোড এ একটু পরিবর্তন আনি।

আমরা তাহলে আগের থেকে Efficient একটা কোড পেলাম। আচ্ছা এর থেকেও কি Efficient কোড করা যায়? এই প্রশ্নের উত্তর একটু পরে খুঁজি । তার আগে আরেকটা ব্যাপার দেখি আমরা।

১০০ = ১ * ১০০

     ২ * ৫০

     ৪ * ২৫

৫ * ২০

১০ * ১০

এখানে আমরা ১০০ এর Divisor গুলো বের করলাম। আমরা যদি জোড়া করি Divisor গুলোর তাহলে দেখবো ১ , ২ , ৪ , ৫ , ১০ এই সংখ্যাগুলো দিয়ে ১০০ কে ভাগ করলে আমরা ১০০ , ৫০ , ২৫ , ২০ , ১০ এগুলো পেয়ে যাচ্ছি। মজার ব্যাপার। তাহলে আমি সর্বনিম্ন কোন সংখ্যা পর্যন্ত চেক করলে সবগুলো Divisor পেয়ে যাচ্ছি ? ১০ পর্যন্ত। লক্ষ্য করলেই দেখবো যে ১০ ১০০ এর বর্গমূলের সমান। আমরা চাইলে অন্যান্য সংখ্যা দিয়েও চেক করে দেখতে পারি। প্রতিবারই আমরা দেখবো যে আমরা কোন সংখ্যার বর্গমূলের ভেতর চেক করলেই সবগুলো Divisor বের করতে পারব। তাহলে আমরা আমাদের আগের প্রশ্নের উত্তর পেয়ে গেলাম।আমরা কোন সংখ্যার Square Root পর্যন্ত লুপ চালালেই বের করতে পারবো সংখ্যাটি প্রাইম কিনা। এবার কোডে আসি।

যাক, এতক্ষণে আমরা অনেক Efficient একটা কোড পেলাম। এভাবেই তাহলে আমরা কোন সংখ্যা প্রাইম কিনা তা বের করতে পারবো।

এখন আমরা জানবো কিভাবে একটা সংখ্যার প্রাইম ফ্যাক্টর গুলো প্রিন্ট করতে হয়। একটি সংখ্যা নেই। ধরলাম ৩৬০। এর প্রাইম ফ্যাক্টরগুলো হল ২ ২ ২ ৩ ৩ ৫। অর্থাৎ এই প্রাইম গুলো গুন করলে আমরা ৩৬০ পাবো। এখন আমরা কিভাবে প্রিন্ট এর কাজ টা করব? আমরা আগের মতই সংখ্যার Square Root পর্যন্ত লুপ চালাবো আর Divisor পেলেই সেটাকে ওই সংখ্যা থেকে বাদ দিয়ে দিব। কোডে দেখি ব্যাপার টা।

কোড দেখে ঘাবড়ানোর কিছু নেই। ধীরে ধীরে আমরা দেখি কোডের প্রসেস। আমরা আমাদের প্ল্যান অনুযায়ী Square Root পর্যন্ত লুপ চালালাম। তারপর যদি কোন Divisor পাই তাহলে চেক এর ভেতরের While লুপ এর মাধ্যমে আমরা ওই সংখ্যা থেকে Divisor টা সম্পূর্ণভাবে বাদ দিয়ে দিচ্ছি আর প্রিন্ট করতেসি প্রতিবার। এখন এই কোড দেখে অনেক প্রশ্নই মনে জাগবে। আমরা যে Divisor বাদ দিচ্ছি তা যে Prime Divisor / Factor তার গ্যারান্টি কি? বা কোড এর শেষে আমরা যে অতিরিক্ত ( N > 1 ) এর চেক দিলাম তার দরকারই বা কি?

প্রথম প্রশ্নের উত্তরে আসি। যদি সংখ্যাটি জোড় হয় তাহলে তার Divisor গুলোর মাঝে ২ অবশ্যই থাকবে। আমরা যদি সবগুলো ২ কেই বাদ দিয়ে দেই তাহলে নতুন করে আর কোন জোড় Divisor পাওয়ার সম্ভাবনা রইলনা। বাকি রইল বিজোড় Divisor গুলো। যদি ৩ থাকে তাহলে ৩ বাদ দেয়ার সময় ৩ এর গুণিতক থাকলে এগুলোও বাদ পরে যাচ্ছে। তাই পরবর্তীতে লুপ এ আমরা ৩ এর কোন গুণিতক কে Divisor হিসেবে পাবোনা। তাহলে বোঝাই যাচ্ছে যে আমরা লুপ এর কন্ডিশন অনুযায়ী শুধু প্রাইম সংখ্যাগুলো কে Factor / Divisor হিসেবে পাচ্ছি।

এবার দ্বিতীয় প্রশ্ন এর উত্তর। আমরা কোড থেকে এটুকু অবশ্যই বুঝতে পারছি যে N কে ভাগ করার পর N ছোট হয়ে যাচ্ছে। তার ফলে আমাদের বাইরের লুপটার কন্ডিশন ও ছোট হচ্ছে। তাহলে এমন একটা পর্যায় আসবে যখন দুইটা প্রাইম গুন আকারে থাকবে। অথবা একটা প্রাইম থেকে যাবে। ধরি P1 আর P2 দুইটা প্রাইম সংখ্যা (P1 <= P2)। এখন এদের গুনফলের Square root যদি আমরা বের করি তাহলে (P1 <= Square root(P1,P2) <= P2) হবে। লুপের কন্ডিশন অনুযায়ী P1 আমরা বাদ দিয়ে দিব। এখন P2 এর কি হবে ? এর Square root তো এর থেকে ছোট। তাই এইটা চেক হওয়ার আগেই লুপ Terminate হয়ে যাচ্ছে। তাই আমরা অতিরিক্ত একটি চেক দিলাম যে N ১ এর চেয়ে বড় থাকলে সেটাও আমরা প্রিন্ট করে দিব।

আজ তাহলে এ পর্যন্তই। এর পরের টিউটোরিয়াল এ আমরা দেখবো কিভাবে ১০^৭ পর্যন্ত প্রাইম সংখ্যা সহজেই বের করা যায়।

Euler's Totient or phi function φ(n)

phi ফাংশন কি?

phi ফাংশন একটি arithmetic function যেটি count করে একটি সংখ্যা N এর সমান বা ছোট কতটি ধনাত্মক সংখ্যা আছে যেগুলো N এর relative prime. অর্থাৎ 1 থেকে শুরু করে N পর্যন্ত মোট কতটি সংখ্যা আছে যেগুলোর সাথে N এর 1 বাদে অন্য কোন common divisor নেই, আরেকটু সহজ করে বলতে গেলে যাদের সাথে N এর GCD = 1. উদাহরন দিলেই ব্যাপারটা আরও পরিষ্কার হবে।

8(eight) সংখ্যাটিকে ধরি, এর সমান ও ছোট ধনাত্মক সংখ্যাগুলো হল,
1 2 3 4 5 6 7 8
এর মধ্যে থেকে 8 এর সাথে common divisor আছে এমন সংখ্যাগুলোকে বাদ দেই,
1 2 3 4 5 6 7 8
তাহলে 4 টি সংখ্যা অবশিষ্ট থাকে 1 3 5 7. অর্থাৎ φ(8) = 4.

আবার 15 সংখ্যাটি বিবেচনা করি,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
অবশিষ্ট থাকে 8 টি সংখ্যা – 1, 2, 4, 7, 8, 11, 13, 14
অর্থাৎ φ(15) = 8.

এখন চিন্তা করি prime number এর ক্ষেত্রে phi function এর চেহারা কেমন হবে। উত্তরটা খুব সহজ। কোন একটি সংখ্যা prime এর মানেই হল সংখ্যাটির 1 বাদে অন্য কোন divisor নেই যেটি সংখ্যাটি থেকে ছোট।
সুতরাং φ(prime) = prime-1.

7 সংখ্যাটি একটি prime number. তাহলে 7 এর জন্য,
1 2 3 4 5 6 7

so, φ(7) = 7-1
so, φ(prime) = prime-1

Some Properties

phi ফাংশনের কাজ করার মত algorithm লিখতে হলে আমাদেরকে এর কয়েকটি basic properties সম্পর্কে জানতে হবে।

1. প্রথমটি উপরেই বর্ণিত। φ(prime) = prime-1.

2. ধরি P একটি prime নাম্বার। P এর যেকোনো পাওয়ার a হলে,

3. অত্যন্ত গুরুত্বপূর্ণ। ফাংশনটি একটি multiplicative ফাংশন। ব্যাখ্যা করি।
ধরি a এবং b দুইটি relative prime number অর্থাৎ এদের মধ্যে 1 ব্যাতিত কোন common divisor নেই। তাহলে a*b এর জন্য ফাংশনটির চেহারা হবে,

Building an Algorithm

উপরের properties গুলোকে ব্যাবহার করে যেকোনো নাম্বারের phi function value বের করার মত পদ্ধতি বের করা যাক। প্রথমেই একটুখানি গনিত প্রয়োজন।

আমরা যেই নাম্বারটির phi function value বের করব সেটিকে তার prime factor এ ভেঙ্গে ফেলব। এটাই আমাদের algorithom এর ভিত্তি হবে।

ধরি একটি নাম্বার n. একে prime factor এ ভেঙ্গে লিখলে হবে,

এখানে n এর factor এর সংখ্যা k টি। এবং P একটি factor হলে a তার পাওয়ার। তাহলে,

এই শেষের লাইনটাই আমাদের দরকার।

আমরা লুপ চালিয়ে একটা একটা করে n এর prime factor গুলা (P1, P2, P3, ……, Pk) নিব এবং প্রত্যেকবার একটা অপারেশন করব। কি করব বলি, সুবিধার জন্য ধরি n এর factor এর সংখ্যা দুইটি। তাহলে,

এই অবশিষ্ট another_something ই হবে আমাদের রেজাল্ট।

অর্থাৎ আমরা একটা variable এ প্রথমে n এর value টা রাখব। ধরি variable টার নাম result। তারপর একটা একটা করে factor P ধরব এবং result কে P দিয়ে ভাগ করে ভাগফলটাকে result থেকে বাদ দিব। এভাবে ক্রমাগত factor গুলা দিয়ে ভাগ এবং বিয়োগ করতে থাকলে result এর ভ্যালু কমতে থাকবে। সবশেষে যা পড়ে থাকবে তাই আমাদের φ(n).

বিশেষ দ্রষ্টব্যঃ prime factor কিভাবে বের করতে হয় সেটা না জানলে পরের code টুকু বুঝতে কষ্ট হবে। সেক্ষেত্রে prime factor বের করাটা আগে শিখে নেওয়া ভাল। এটাই এই অ্যালগরিদমের ভিত্তি।

A possible C++ Implementation

Some UVA Problems

Happy coding.

Md. Fahim Mohiuddin Dhrubo
11 October 2014