$-১৭$ কে $৫$ দিয়ে ভাগ করলে ভাগশেষ কত হয়? $২^{১০০০}$ কে $১৭$ দিয়ে ভাগ করলে ভাগশেষ কত হয় সেটা কি তুমি ওভারফ্লো এড়িয়ে নির্ণয় করতে পারবে? $O(n)$ এ পারলে $O(\log_2 {n})$ কমপ্লেক্সিটিতে পারবে? যদি কোনো একটি উত্তর "না" হয় তাহলে এই পোস্ট তোমার জন্য। তবে তুমি যদি মডুলার ইনভার্স বা এডভান্সড কিছু শিখতে পোস্টটি খুলো তাহলে তোমাকে আপাতত হতাশ করতে হচ্ছে।
সি/জাভা সহ বেশিভাগ প্রোগ্রামিং ল্যাংগুয়েজে এ $\%$ কে ভাগশেষ অপারেটর ধরা হয়। $x$ কে $m$ দিয়ে ভাগকরে ভাগশেষ বের করার অর্থ $x\%m$ এর মান বের করা অথবা আমরা বলতে পারি $x$ কে $m$ দিয়ে mod করা। "determine answer modulo 1000" এ কথাটির অর্থ হলো উত্তরকে...
Read More
নাম্বার থিওরী
বিটওয়াইজ্ সিভ(Bitwise sieve)
বিটওয়াইজ সিভ প্রাইম সংখ্যা বের করার জন্য প্রচলিত অ্যালগোরিদম Sieve of Eratosthene এ মেমরির ব্যবহার অনেক কমিয়ে আনা যায়! সাধারণ সিভে N পর্যন্ত প্রাইম জেনারেট করলে N সাইজের একটি অ্যারে ডিক্লেয়ার করতে হয়। অ্যরের প্রতিটি এলিমেন্ট একটি করে ফ্ল্যাগ হিসাবে কাজ করে যেটা দেখে আমরা বুঝি একটি সংখ্যা প্রাইম নাকি কম্পোজিট। বিটওয়াইজ্ সিভে আমরা ফ্ল্যাগ হিসাবে ইন্টিজার বা বুলিয়ান এর বদলে সরাসরি বিট ব্যবহার করবো।
এ টিউটোরিয়াল পড়ার আগে দুটি বিষয় তোমাকে জেনে আসতে হবে
১. Sieve of Eratosthene এর সাধারণ ভার্সণ,তুমি এটা আমার এই পোস্টটি পড়ে শিখতে পারবে সহজেই।
২. সি/সি++ এ বিটওয়াইজ্ অপারেটরের ব্যবহার। এট...
Read More
প্রাইম জেনারেটর (Sieve of Eratosthenes)
প্রাচীনকাল থেকেই গণিতবিদরা মাথা ঘামাচ্ছেন প্রাইম নাম্বার বা মৌলিক সংখ্যা নিয়ে। প্রাইম নাম্বারগুলো মধ্যে লুকিয়ে আছে বিষ্ময়কর কিছু সৌন্দর্য। যেকোনো কম্পোজিট বা যৌগিক সংখ্যাকে একাধিক প্রাইমের গুণফল হিসাবে মাত্র একভাবে লেখা যায়,ঠিক যেমন সব যৌগিক পদার্থ একাধিক মৌলিক পদার্থের সমন্বয়ে তৈরি। প্রাচীনকাল থেকেই মানুষ প্রাইম নিয়ে গবেষণা করছে,চলছে এখনো। গাউস,ফার্মা,ইউলারের মত কিংবদন্তি গণিতবিদরা কাজ করেছেন প্রাইম নিয়ে।
দ্রুত গতিতে প্রাইম সংখ্যা বের করার একটি পদ্ধতি আবিষ্কার করেন Eratosthenes,২০০ খ্রিস্টপূর্বের একজন গ্রীক গণিতবিদ,বিজ্ঞানি ও কবি। ২২০০ বছরেরও পুরানো সেই পদ্ধতি ব্যবহার করে আমরা আধুনিক...
Read More