فرادرسالگوریتم یافتن اعداد متباین (Coprime) در جاوا — به زبان ساده
دو عدد a و b زمانی اعداد متباین یا نسبت به هم اول نامیده می‌شوند که تنها عامل یا فاکتور مشترک آن‌ها عدد 1 باشد. این نوع اعداد به نام «متقابلاً اول» (Mutually prime) یا coprime نیز نامیده می‌شوند. در این راهنما به بررسی اول بودن دو عدد نسبت به هم در زبان برنامه‌نویسی جاوا می‌پردازیم.
الگوریتم یافتن بزرگترین عامل مشترک
چنان که اشاره کردیم اگر بزرگترین مقسوم‌علیه مشترک دو عدد a و b برابر با 1 باشد، در این صورت a و b نسبت به هم اول یا اعداد متباین هستند. در نتیجه برای تعیین این که آیا دو عدد نسبت به هم اول هستند یا نه، کافی است بررسی کنیم که بزرگترین مقسوم‌علیه مشترک آن‌ها 1 باشد.
پیاده‌سازی الگوریتم اقلیدس
در این بخش از الگوریتم اقلیدس برای محاسبه بزرگترین مقسوم‌علیه مشترک اعداد استفاده می‌کنیم. پیش از آن که این پیاده‌سازی را ارائه کنیم، اقدام به جمع‌بندی الگوریتم خود کرده و یک مثال کوچک در مورد شیوه استفاده از آن را بررسی می‌کنیم تا عملکردش را درک کنیم.
بنابراین تصور کنید دو عدد صحیح به نام‌های a و b داریم. با بهره‌گیری از یک رویکرد مبتنی بر حلقه تکرار، ابتدا a را بر b تقسیم کرده و باقیمانده را به دست می‌آوریم. سپس مقدار a را برابر با b می‌گیریم و مقدار b را نیز برابر با باقیمانده در نظر می‌گیریم. این فرایند را تا زمانی که b=0 شود ادامه می‌دهیم. در نهایت زمانی که به این نقطه برسیم، مقدار a را به عنوان بزرگترین مقسوم‌علیه مشترک بازگشت می‌دهیم و اگر a = 1 باشد می‌گوییم که a و b نسبت به هم اول هستند.
این فرایند را با دو عدد a = 81 و b = 35 بررسی می‌کنیم. در این حالت باقیمانده تقسیم 81 بر 35 برابر با 11 است. بنابراین در گام نخست فرایند تکراری خود، مقادیر a = 35 و b = 11 به دست می‌آیند. متعاقباً یک مرحله دیگر از تکرار را اجرا می‌کنیم.
باقیمانده تقسیم 35 بر 11 برابر با 2 است. در نتیجه ما اینک مقدار a = 11 و b = 2 را داریم، چون جای مقادیر را با هم عوض کرده‌ایم. به این کار ادامه می‌دهیم و در گام بعدی، نتیجه a = 2 و b = 1 به دست می‌آید. اینک به هدف خود نزدیک شده‌ایم.
در نهایت پس از یک تکرار دیگر، به مقادیر a = 1 و b = 0 می‌رسیم. این الگوریتم مقدار 1 را بازگشت می‌دهد و می‌توانیم نتیجه بگیریم که 81 و 5 واقعاً نسبت به هم اول هستند.
پیاده‌سازی دستوری
ابتدا یک نسخه از برنامه دستوری جاوا را برای الگوریتم اقلیدسی چنان که در بخش قبل توضیح دادیم، پیاده‌سازی می‌کنیم.
1int iterativeGCD(int a, int b) {
2 int tmp;
3 while (b != 0) {
4 if (a < b) {
5 tmp = a;
6 a = b;
7 b = tmp;
8 }
9 tmp = b;
10 b = a % b;
11 a = tmp;
12 }
13 return a;
14}همان طور که می‌توان مشاهده کرد، در حالتی که a کمتر از b باشد، مقادیر را پیش از شمارش جابجا می‌کنیم. این الگوریتم زمانی که b برابر با 0 باشد متوقف می‌شود.
پیاده‌سازی بازگشتی
در ادامه پیاده‌سازی بازگشتی این الگوریتم را نیز بررسی می‌کنیم. این نسخه احتمالاً تمیزتر است، زیرا از تعویض صریح مقادیر متغیرها خودداری کرده‌ایم:
1int recursiveGCD(int a, int b) {
2 if (b == 0) {
3 return a;
4 }
5 if (a < b) {
6 return recursiveGCD(b, a);
7 }
8 return recursiveGCD(b, a % b);
9}استفاده از پیاده‌سازی BigInteger
شاید برایتان سؤال پیش آمده باشد که آیا الگوریتم یافتن بزرگترین مقسوم‌علیه مشترک قبلاً در جاوا پیاده‌سازی شده است یا نه؟ البته که شده است. کلاس BigInteger یک روش برای یافتن بزرگترین مقسوم‌علیه مشترک ارائه می‌کند که به پیاده‌سازی الگوریتم اقلیدسی به این منظور پرداخته است. با استفاده از این روش می‌توان الگوریتم یافتن اعداد متباین را به روش ساده‌تری بازنویسی کرد:
1boolean bigIntegerRelativelyPrime(int a, int b) {
2 return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).equals(BigInteger.ONE);
3}سخن پایانی
در این راهنمای کوتاه به یک راه‌حل برای مسئله یافتن وضعیت اول بودن دو عدد نسبت به هم پرداختیم و سه پیاده‌سازی مختلف برای الگوریتم یافتن بزرگترین مقسوم‌علیه مشترک معرفی کردیم. برای مشاهده کد منبع این مثال‌ها می‌توانید به این آدرس گیت‌هاب (+) مراجعه کنید.
اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزش‌های ریاضیات
- آموزش طراحی الگوریتم به همراه حل مثال‌های عملی
- مجموعه آموزش‌های جاوا (Java)
- اعداد اول — به زبان ساده
- تجزیه اعداد — به زبان ساده
- فهرست مطالب ریاضی وبلاگ فرادرس
==
