این مباحث اولیه برای حل مسایل ضروری هستند اما کافی نیستند.
هدف پیدا کردن اعداد اول در یک بازه مشخص است.
یک آرایه ۰ و ۱ به اندازه بزرگترین عددی که میخواهیم اول بودن آن را بررسی کنیم میسازیم. ابتدا علامت خانه متناظر ۲ را ۱ (به معنی اول) قرار میدهیم. سپس یک حلقه تکرار از ۳ تا $n$ (بزرگترین عدد مورد نظر) ایجاد میکنیم و درون آن بخشپذیری آن را بر اعداد کمتر یا مساوی از $\sqrt n$ بررسی میکنیم.
زمان این الگوریتم $O(n\sqrt n)$ است و حافظه $O(n)$ میبرد.
دو روش برای پیدا کردن بزرگترین مقسوم علیه مشترک و کوچکترین مضرب مشترک دو عدد را در ادامه خواهید دید.
روش اول تجزیه کردن اعداد به عوامل اول آنها و به دست آوردن اشتراک بین این عوامل اول است. حاصل ضرب عوامل اول مشترک ب.م.م دو عدد را میدهد. برای تجزیه یک عدد، از یک حلقه تکرار استفاده میکنیم که در آن ابتدا عدد داده شده را تا زمانی که بخشپذیر است به ۲ تقسیم میکنیم و تعداد این عوامل ۲ را هم نگه میداریم. سپس این کار را برای عدد بعدی (۳) انجام میدهیم تا زمانی که عدد اولیه به ۱ برسد.
روش دیگری با استفاده از همنهشتی برای پیدا کردن ب.م.م وجود دارد. فرض کنید میخواهیم ب.م.م دو عدد $a$ و $b$ را به دست بیاوریم. میدانیم: \[ GCD(a,b) = GCD(a,b-a) = GCD(a-b,a) \] این تساوی هنگامی برقرار است که اعداد مثبت بمانند، پس هر بار عدد کوچکتر را از عدد بزرگتر کم میکنیم تا به جایی برسیم که دو عدد مساوی شوند که همان ب.م.م است.
زمان این کار خیلی زیاد است، پس برای حل این مشکل بهبودهایی روی این روش انجام میدهیم. میدانیم تا زمانی که به باقیمانده تقسیم $a$ بر $b$ نرسیدهایم، میتوانیم عمل تفاضل را انجام دهیم. اگر باقیماندهگیری را با عملگر ٪ نشان دهیم، داریم: \[ GCD(a,b) = GCD(a\%b,b) \] برای ک.م.م میدانیم: \[ LCM(a,b) = \frac{a\times b}{GCD(a,b)} = a\times \frac{b}{GCD(a,b)} \] مزیت این کار کوچک کردن اعداد است که به ازای اعداد بزرگ سرریز نکنند.
چون رشد این تابع زیاد است پیشنهاد میشود از کتابخانه اعداد بزرگ جاوا استفاده کنید.
دنباله فیبوناچی یک دنباله بازگشتی پرکاربرد است. میتوان آن را با استفاده از برنامهریزی پویا با استفاده از رابطه بازگشتی آن محاسبه کرد: \[ Fib(n) = Fib(n-1)+Fib(n-2),\quad Fib(0)=Fib(1) = 1 \] از ویژگیهای این اعداد این است که هر عدد را میتوان در مبنای فیبوناچی نوشت، یعنی به صورت مجموع اعداد فیبوناچی غیرتکراری که هیچ دو عدد فیبوناچی متوالی در آنها نباشد.
رشد این دنباله هم سریع است و بهتر است برای پیادهسازی آن از اعداد بزرگ استفاده شود.