מצא אם שני מספרים הם ראשוניים יחסית ב- Java
1. סקירה כללית
בהינתן שני מספרים שלמים, א ו ב, אנו אומרים שהם כן ראשוני יחסית אם הגורם היחיד שמחלק את שניהם הוא 1. ראשוני או קופרימי הדדי הם מילים נרדפות למספרים ראשוניים יחסית.
במדריך מהיר זה, נעבור על פיתרון לבעיה זו באמצעות Java.
2. האלגוריתם הגדול ביותר של גורמים נפוצים
כפי שמתברר, אם המחלק המשותף הגדול ביותר (gcd) של 2 מספרים א ו ב הוא 1 (כלומר gcd (a, b) = 1) לאחר מכן א ו ב הם ראשוניים יחסית. כתוצאה מכך, קביעת האם שני מספרים הם ראשוניים יחסית מורכבת פשוט מלמצוא אם ה- gcd הוא 1.
3. יישום האלגוריתם האוקלידי
בחלק זה נשתמש באלגוריתם האוקלידי לחישוב ה- gcd של 2 מספרים.
לפני שנציג את היישום שלנו, בואו נסכם את האלגוריתם ונראה דוגמה מהירה כיצד ליישם אותו לשם הבנה.
אז דמיין שיש לנו שני מספרים שלמים, א ו ב. בגישה האיטרטיבית אנו מתחלקים תחילה א על ידי ב ולקבל את השאר. לאחר מכן אנו מקצים א הערך של ב, ואנחנו מקצים ב הערך הנותר. אנו חוזרים על תהליך זה עד ב = 0. לבסוף, כאשר אנו מגיעים לנקודה זו, אנו מחזירים את הערך של א כמו gcd תוצאה, ואם א = 1, אנחנו יכולים לומר את זה א ו ב הם ראשוניים יחסית.
בואו ננסה את זה בשני מספרים שלמים, a = 81 ו b = 35.
במקרה זה, יתרת 81 ו 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 ו 35 הם אכן ראשוניים יחסית.
3.1. יישום הכרחי
ראשית, בואו נשתמש בגרסת Java החובה של האלגוריתם האוקלידי כמתואר לעיל:
int iterativeGCD (int a, int b) {int tmp; ואילו (b! = 0) {if (a <b) {tmp = a; a = b; b = tmp; } tmp = b; b = a% b; a = tmp; } להחזיר a; } כפי שאנו יכולים להבחין, במקרה בו א זה פחות מ ב, אנו מחליפים את הערכים לפני שנמשיך. האלגוריתם נעצר מתי ב הוא 0.
3.2. יישום רקורסיבי
לאחר מכן, בואו נסתכל על יישום רקורסיבי. זה כנראה נקי יותר מכיוון שהוא מונע החלפות ערכים משתנות מפורשות:
int recursiveGCD (int a, int b) {if (b == 0) {return a; } אם (a <b) {return recursiveGCD (b, a); } להחזיר רקורסיבית GCD (b,% b); } 4. שימוש ביג-שלםיישום
אבל רגע - זה לא gcd אלגוריתם שכבר יושם בג'אווה? כן זה כן! ה ביג-שלם הכיתה מספקת א gcd שיטה המיישמת את האלגוריתם האוקלידי למציאת המחלק המשותף הגדול ביותר.
באמצעות שיטה זו אנו יכולים לנסח ביתר קלות את האלגוריתם העיקרי יחסית כ:
bigIntegerRelativelyPrime (int a, int b) {להחזיר BigInteger.valueOf (a) .gcd (BigInteger.valueOf (b)). שווה (BigInteger.ONE); } 5. מסקנה
במדריך מהיר זה, הצגנו פתרון לבעיה למצוא אם שני מספרים הם ראשוניים יחסית באמצעות שלוש יישומים של gcd אַלגוֹרִיתְם.
וכמו תמיד, קוד הדוגמה זמין ב- GitHub.
