ট্রায়েল ডিভিশন

সমস্যাটি সংজ্ঞায়িত কর

আমাদের এমন একটি যন্ত্র তৈরি করতে হবে যেটা সাধারণ হ্যাঁ/না প্রশ্নের উত্তর দিতে পারবে। একটি পূর্ণ সংখ্যা n যদি ইনপুট হিসাবে দেওয়া হয়, n কি মৌলিক সংখ্যা?

এখন মেশিনের ভিতরে কি থাকলে মেশিনটি কাজ করবে তা চিন্তা করা যাক। মেশিন শুধুমাত্র কিছু নির্দেশনার উপরে ভিত্তি করে কিছু ক্রমধারা অনুসরণ করে কাজ করতে পারে, আর এই নির্দেশনাকে আমরা algorithm (অ্যালগোরিদম) বলে থাকি। এখন তোমার মাথার ভিতরে কোন অ্যালগোরিদমটি আছে তা খুঁজে বের করা যাক। এই প্রশ্নটির উত্তরটি খুঁজে বের করা যাক: 49 সংখ্যাটি কি একটি মৌলিক সংখ্যা?

…

না? তুমি এটা কীভাবে করলে? তুমি 49 সংখ্যাটির একটি ভাজক খুঁজে বের করার চেষ্টা করেছ যে সংখ্যাটি 1 থেকে বড় এবং 49 থেকে ছোট হবে। তুমি যদি তোমার নামতার ঘর মুখস্ত করে না রাখ তাহলে তুমি নিচের এই ধারাটি অনুসরণ করতে পার:

49 সংখ্যাটি কি 2 দিয়ে বিভাজ্য? না
49সংখ্যাটি কি 3 দিয়ে বিভাজ্য? না
49 সংখ্যাটি কি 4 দিয়ে বিভাজ্য? না
49 সংখ্যাটি কি 5 দিয়ে বিভাজ্য? না
49 সংখ্যাটি কি 6 দিয়ে বিভাজ্য? না
49 সংখ্যাটি কি 7 দিয়ে বিভাজ্য? হ্যাঁ

আমরা 49 এর একটি ভাজক খুঁজে পেয়েছি (7) যেটা প্রমান করে যে 49 একটি যৌগিক সংখ্যা।

একটি দেয়াল তৈরি করা

আমরা এখন যদি প্রশ্ন করি যে 2971215073 সংখ্যাটি কি একটি মৌলিক সংখ্যা?

তুমি কি এখনও পরীক্ষা করে দেখছ? প্রথম কয়েক হাজার পরীক্ষা করার পরেও আমি এখনও কোন ভাজক খুঁজে পাইনি। এখানে মূল প্রশ্নটি হল, আমরা কখন পরীক্ষা করা বাদ দিতে পারব এবং প্রমান করতে পারব যে n একটি মৌলিক সংখ্যা? (এটাকে এখন আমাদের দেয়াল বলা যাক) শুরু থেকেই আমরা বলতে পারি যে, আমরা জানি যে আমাদের দেয়ালটিকে n-1 হতে হবে (কেননা n কে n দিয়ে ভাগ করা সম্ভব)। আমরা যদি 2971215072 সংখ্যাটি পর্যন্ত পরীক্ষা করে দেখি যেআমরা একটি ভাজক খুঁজে পাই কিনা (যেটা প্রমান করবে যে n একটি যৌগিক সংখ্যা) অথবা আমরা কোন ভাজক খুঁজে পাব না (যেটা প্রমান করবে যে n একটি মৌলিক সংখ্যা)।

আরও ভাল একটি দেয়াল তৈরি করা

এটি কাজ করবে, কিন্তু আমরা কি দেয়ালটি আরও ভালভাবে তৈরি করতে পারি যেটা ব্যবহার করলে আমাদের সময় বাচবে? এখানে মনে রাখা দরকার যে আমরা আসলে সবার প্রথম (অথবা সবচেয়ে ছোট) ভাজকটি খুঁজছি। কোন কোন সময় সবচেয়ে ছোট ভাজকটি 2 হতে পারে, আবার এর থেকে বড় সংখ্যার ভাজকও হতে পারে। যেটা আমাদেরকে আমাদের সবচেয়ে মূল প্রশ্নে নিয়ে আসে: সবচেয়ে ছোট সংখ্যার ভাজকটি কত বড় হতে পারে?

এখানে মনে রাখা দরকার যে যে কোন মিশ্র পূর্ণসংখ্যা n, দুইটি বা তার চেয়ে বেশি মৌলিক সংখ্যার মাধ্যমে তৈরি করা হয় n= P * P …

P হল সবচেয়ে বড় যখন n এর যথাযথভাবে দুইটি ভাজক থাকে যারা একে অপরের সমান হবে। এটাকে আমরা square number (বর্গ সংখ্যা) বলে থাকি, যেমন 9 (9 = 33) অথবা 49 (49 = 77)। আমরা এখানে যে কাজটি করব সেটা হল, আমরা আমাদের দেয়ালটি n এর বর্গমূল হিসেবে তৈরি করব!

নিজে থেকেই এই বিষয়টি উপলব্ধি কর: যদি তুমি n এর বর্গমূলটি পরীক্ষা করে দেখার পরে তুমি যদি n এর একটি ভাজক খুঁজে বের করতে না পার, তাহলে n অবশ্যই একটি মৌলিক সংখ্যা হবে। নিজে থেকেই এই বিষয়টি প্রমান করার চেষ্টা কর (এই প্রবন্ধের একদম নিচে একটি প্রমান দেওয়া আছে)

Trial division algorithm (ট্রায়েল ডিভিশন অ্যালগোরিদম)

এবার, আমরা সামনে এগিয়ে যাবার জন্য তৈরি। কিন্তু প্রথমে আমাদের ট্রায়েল ডিভিশন অ্যালগোরিদমটি একদম সাধারনভাবে সংক্ষিপ্তভাবে বলা যাক:

যেকোন পূর্ণসংখ্যা n ইনপুট হিসেবে নেওয়া যাক
{2 ... sqrt(n)} থেকে শুরু হওয়া প্রতিটি পূর্ণসংখ্যা x এর জন্য পরীক্ষা করে দেখতে হবে যে x সংখ্যাটি দিয়ে n সংখ্যাটি ভাগ করা যায় কিনা
যদি একটি ভাজক খুঁজে পাও তাহলে n একটি যৌগিক সংখ্যা আর অন্যথায় n একটি মৌলিক সংখ্যা

তোমার যদি প্রোগ্রামিং সম্পর্কে অভিজ্ঞতা থাকে তাহলে তুমি CSscratchpad প্রোগ্রামটি খুলে এই ফাংশনটি পরীক্ষা করে দেখতে পার এবং দেখতে পার যে এই ফাংশনটি কাজ করছে কিনা। যদি এটা কাজ না করে, তাহলে তুমি পরবর্তী ধাপের দিকে অগ্রসর হতে পার যেখানে আমি এই ফাংশনটি কাজ করছে এমন একটি ভার্শন দিয়ে রেখেছি, যেখান থেকে তুমি তোমার কাজ শুরু করতে পার। (FYI কোন প্রকার প্রোগ্রামিং অনুশীলন না করেও, এই অনুশীলনটি করা সম্ভব)।

আলোচনায় অংশ নিতে চাও?

প্রবেশ কর

সাজানো আছেঃ

কোন আলাপচারিতা নেই।

ইংরেজি জানো? খান একাডেমির ইংরেজি সাইটে আরো আলোচনা দেখতে এখানে ক্লিক কর।