মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 2
পাঠ 6: মৌলিক সংখ্যা যাচাই- ভূমিকা
- মৌলিক সংখ্যা যাচাই সংক্রান্ত চ্যালেঞ্জ
- ট্রায়েল ডিভিশন
- কম্পিউটার মেমোরি কি?
- অ্যালগোরিদমিক কর্মক্ষমতা
- লেভেল 3: চ্যালেঞ্জ
- সিয়েভ অফ ইরাটোসথেন্স
- লেভেল 4: সিয়েভ অফ ইরাটোসথেন্স
- সিয়েভ ব্যবহার করে মৌলিক সংখ্যা যাচাই পরীক্ষা
- লেভেল 5: সিয়েভ ব্যবহার করে ট্রায়েল ডিভিশন
- মৌলিক সংখ্যার তত্ত্ব
- মৌলিক সংখ্যার ঘনত্ব সংক্রান্ত চক্র
- মৌলিক সংখ্যার মধ্যে থাকা ফাঁকা স্থান
- স্থান কালের ট্রেডঅফ
- সার-সংক্ষেপ (এরপরে কি?)
© 2023 Khan Academyব্যবহারের শর্তাদিগোপনীয়তার নীতিমালাকুকি নোটিশ
সিয়েভ ব্যবহার করে মৌলিক সংখ্যা যাচাই পরীক্ষা
সিয়েভ অফ ইরাটোসথেন্স ব্যবহার করে সন্তোষজনক ট্রায়েল ডিভিশনের মৌলিক সংখ্যা যাচাই সংক্রান্ত পরীক্ষাটি করতে চেষ্টা কর। এটি তৈরি করেছে ব্রিট ক্রুজ
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।
ভিডিও ট্রান্সক্রিপ্ট
## আগামী ও গ্রামীণফোন এর সহযোগিতায় অনূদিত ## এখন, পুনরাবৃত্তিতে কোন সংখ্যার সমষ্টি N মৌলিক তা কিনা তা আমরা পরীক্ষামূলকভাবে যাচাই করছি। এখানে N এর বর্গমূল এবং এখানে তিন রয়েছে। তিন থেকে শুরু করে, আমরা দুই করে N এর বর্গমূল পর্যন্ত যাচ্ছি। এর মধ্যে প্রত্যেক বিন্দুতে, যাচাই করছি ঐ বিন্দু দ্বারা N কে ভাগ করা যায় কিনা। এখন পর্যন্ত, আমরা হয়তো পরে শুরু করে বা বড় ধাপ নিয়ে যে ধাপগুলো সম্পন্ন করেছি, মানুষ তা কমানোর চেষ্টা করছে। আমি এখানে একটু থামতে চাই এবং এসো চিন্তা করি যে একটি পরীক্ষামূলক বণ্টনের এলগরিদমের আদর্শ ক্ষেত্র কী হবে? ধাপগুলো কার্যকরী করতে আমরা সম্ভাব্য সর্বোচ্চ ভালো কী করতে পারি? মনে রেখ, যে কোন সংখ্যা N এর তিনটি উৎপাদক রয়েছে। মনে করি এখানে N এর বর্গমূল আছে। আমাদের আসলে প্রত্যেক ধাপে মৌলিক সংখ্যা প্রয়োজন। সেটাই আমরা সবচেয়ে ভালো করতে পারবো। আমরা জানি যদি আমরা শুধু মৌলিক সংখ্যার ক্রম করি আমরা মূলত একটি উৎপাদক পাবো। এটা যৌগিক হয় তবে তিনটি উৎপাদক হবে। এখন প্রশ্ন হলো এই পদ্ধতি কতটুকু কার্যকর? এটা দেখে মনে হচ্ছে যে এখন আমাদের একটি নির্ভুল সমাধান আছে। যদি আমরা একটি নতুন এলগরিদম লিখি যার নাম প্রথমে ছিল সেইভ। মনে করি, N মৌলিক সংখ্যা ধরে নতুন এলগরদম হিসাব করছে। যদি তুমি সেইভ দিয়ে আমাদের জন্যে একটি সুন্দর দীর্ঘ মৌলিক সংখ্যার তালিকা তৈরি করে দিতে পারো। এরপর আমরা পরীক্ষামূলক যাচাই করবো যা এই মৌলিক সংখ্যার তালিকায় ব্যবহৃত হবে। এটা মৌলিক সংখ্যা নিয়ে কাজ করবে এবং N এর বর্গমূল পর্যন্ত চলবে, এটা যাই হোক। এটার ভুল কোথায়? আমরা সময়ের জটিলতা অথবা ধাপের সংখ্যা দেখতে পারি মনে রেখ আমি এটা করেছিলাম-- আমি এই এলগরিদম উদ্ধৃত করেছিলাম এবং আমি প্রত্যেক লুপের ভিতর একটি ধাপ নির্ণায়ক রেখেছি, তাহলে আমাদের -- মনে করি, ধাপ প্লাস প্লাস মানে আসলে ধাপ যোগ ১। অন্য লুপের ভিতরে, সেখানেও একটি ধাপ নির্ণায়ক রয়েছে। ধাপ প্লাস প্লাস। এই সবগুলো ধ্রুবক ক্রিয়া ইফ ফাংশন যাচাই করছে এবং চিহ্নিত করছে। আমাদের প্রত্যেক লুপের ভিতর একটি ধাপ নির্ণায়ক ছিল। এখন এখানে একটি তুলনা আছে। বামপাশে আমাদের পুরানো পরীক্ষামূলক বণ্টন পদ্ধতি আছে । মাঝে, N সংখ্যক পর্যন্ত সকল মৌলিক সংখ্যা তৈরিতে ব্যবহৃত সেইভ নামে আমাদের এলগরিদম আছে। ডান পাশে এই প্রস্তাবনা আছে যেখানে আমরা সেইভকে N এর বর্গমূল পর্যন্ত মৌলিক সংখ্যা তৈরি করতে রেখেছি এবং এরপর শুধু ঐ মৌলিক সংখ্যাগুলোর ক্ষেত্রে পরীক্ষামূলক বণ্টন পদ্ধতি রেখেছি। চল আমরা দেখি একটি ছোট ইনপুট দিলে কী হয়। প্রাথমিকভাবে আমরা দেখতে পারছি, সেইভ অনেকগুলো ধাপ নিচ্ছে। এমনকি ডানপাশের পরিমার্জিত সংস্করণ আসলে পরীক্ষামূলক বণ্টন পদ্ধতির চেয়ে ধীর। যখন ইনপুট সংখ্যা বাড়ছে, সেইভ এর ধাপ সংখ্যা দ্রুত বাড়ছে। চলো আমরা মাঝের অংশ ভুলে যাই এবং N এর বর্গমূল যোগ পরীক্ষামূলক বন্টন পর্যন্ত, এই শর্তে, পরীক্ষামূলক বন্টন পদ্ধতি বনাম সেইভ
পদ্ধতির তুলনা করি। এখানে আমরা দেখতে পাচ্ছি যে পুরানো পরীক্ষামূলক বন্টন পদ্ধতি অনেক বেশী কার্যকর। আমাদের সেইভ পর্যন্ত N এর বর্গমূল যোগ পরীক্ষামূলক বন্টন পদ্ধতি এর ধাপগুলো অনেক দ্রুত বাড়ছে। এটা আসলে কোন উন্নয়ন নয়। আমি এই তুলনা করতে নিচের প্রোগ্রামটা ব্যবহার করেছিলাম। আমি কীভাবে এটি প্রস্তুত করেছি তার ব্যাখ্যার একটি রেকর্ডিং আছে। এখন তুমি হয়ত অবাক হবে “আমরা যদি অগ্রিম মৌলিক সংখ্যাগুলো হিসাব করি তাহলে কী হবে? প্রথম ধাপ হবে মৌলিক সংখ্যার একটি এ্যারে তৈরি করা এবং এটা হার্ড ড্রাইভে জমা রাখা। এরপর, আমাদের এলগরিদম শুধু পরীক্ষামূলক বণ্টন পদ্ধতি সম্পন্ন করবে এবং এটা কিভাবে মৌলিক সংখ্যাতে থামবে তা সম্পর্কে অবহিত থাকবে কারণ এটা এই প্রস্তাবিত মৌলিক সংখ্যার তালিকা থেকে পড়বে। হয়তো আমাদের মৌলিক সংখ্যার তালিকা ২০ ডিজিট, এমনকি ১০০ ডিজিট পর্যন্ত জমা করে। কেন আমরা এটা করতে পারি না? সমস্যা হলো মেমোরির সীমাবদ্ধতা। যখন আমরা সংখ্যার তালিকা হিসাব করি, যেটা আমরা পরবর্তীতে অনুসন্ধান করব। উদাহরণস্বরুপ, ধরো আমরা এটা হাতে হাতে করেছিলাম। আমরা হিসাব করেছি পাঁচ ছিলো মৌলিক সংখ্যা আমরা এক টুকরা কাগজে পাঁচ লিখি, এবং আমরা এটা একটি ফাইলের কেবিনেটে জমা রাখি। এরপর আমরা সাত পাই, আমরা ওটা একটি ফাইলের কেবিনেটে জমা রাখি। নয়, অথবা ১১, দুঃখিত, ফাইলের কেবিনেটের মধ্যে। এরপর আমাদের মৌলিক সংখ্যা পূর্ণ একটি ফাইলের কেবিনেট থাকবে। এটা হলো আমাদের- একে একটি মৌলিক সংখ্যার এ্যারে হিসেবে চিন্তা করি। এই ফাইলের কেবিনেট কত বড় হবে যদি, ধরি, ২০ ডিজিট পর্যন্ত সব মৌলিক সংখ্যা বা ১০০ ডিজিট পর্যন্ত সব মৌলিক সংখ্যা চেয়েছিলাম? আমরা কি একটি হার্ড ড্রাইভে এই এ্যারে জমা রাখতে পারি? এটা কেন আসলে সম্ভব নয় বুঝতে হলে আমাদের এই মৌলিক এ্যারে, এটা আসলে কত বড় তা বুঝতে একটু গভীরে যেতে হবে, এবং আধুনিক এবং এমনকি ভবিষ্যত কম্পিউটার হার্ডওয়ারের আকার এর সীমাবদ্ধতা কি তা বুঝতে হবে। ## আগামী ও গ্রামীণফোন এর সহযোগিতায় অনূদিত ##