בדוק אם מספר ראשוני ב- Java
1. הקדמה
ראשית, בוא נעבור על תיאוריה בסיסית כלשהי.
במילים פשוטות, מספר הוא ראשוני אם הוא מתחלק רק באחד ובמספר עצמו. המספרים שאינם ראשוניים נקראים מספרים מרוכבים. והמספר הראשון אינו ראשוני ולא מורכב.
במאמר זה נבחן דרכים שונות לבדוק את ראשוניות המספר ב- Java.
2. יישום מותאם אישית
בעזרת גישה זו אנו יכולים לבדוק אם מספר בין 2 ל (שורש ריבועי של המספר) יכול לחלק את המספר במדויק.
ההיגיון הבא יחזור נָכוֹן אם המספר ראשוני:
ציבור בוליאני isPrime (int מספר) {return number> 1 && IntStream.rangeClosed (2, (int) Math.sqrt (number)) .noneMatch (n -> (number% n == 0)); }3. שימוש ביג-שלם
ביג-שלם class משמש בדרך כלל לאחסון מספרים שלמים גדולים בגודל, כלומר כאלה הגדולים מ- 64 ביט. הוא מספק כמה ממשקי API שימושיים לעבודה int ו ארוך ערכים.
אחד ממשקי ה- API האלה הוא ה- isProbablePrime. API זה חוזר שֶׁקֶר אם המספר בהחלט מורכב ומחזיר נָכוֹן אם יש סיכוי כלשהו שהוא יהיה ראשוני. זה שימושי כאשר מתמודדים עם מספרים שלמים גדולים מכיוון שזה יכול להיות חישוב אינטנסיבי למדי לאמת אותם באופן מלא.
הערת צד מהירה - ה isProbablePrime API משתמש במה שמכונה בדיקות ראשוניות "מילר - רבין ולוקאס - להמר" כדי לבדוק אם המספר הוא כנראה ראשוני. במקרים בהם המספר נמוך מ -100 ביטים, משתמשים רק במבחן "מילר - רבין", אחרת, שני המבחנים משמשים לבדיקת ראשוניות המספר.
מבחן "מילר-רבין" חוזר מספר פעמים קבוע כדי לקבוע את ראשוניות המספר וספירת איטרציה זו נקבעת על ידי בדיקה פשוטה הכוללת את אורך הסיבית של המספר ואת ערך הוודאות המועבר ל- API:
isPrime (int מספר) בוליאני ציבורי {BigInteger bigInt = BigInteger.valueOf (number); החזר bigInt.isProbablePrime (100); }4. שימוש במתמטיקה של Apache Commons
Apache Commons Math API מספק שיטה בשם org.apache.commons.math3.primes.Primes, בה נשתמש לבדיקת ראשוניות המספר.
ראשית, עלינו לייבא את ספריית Apache Commons Math על ידי הוספת התלות הבאה שלנו pom.xml:
org.apache.commons commons-math3 3.6.1 הגרסה האחרונה של commons-math3 תוכל למצוא כאן.
נוכל לעשות את הבדיקה רק על ידי קריאה לשיטה:
Primes.isPrime (מספר);5. מסקנה
בכתב מהיר זה ראינו שלוש דרכים לבדוק את ראשוניות המספר.
את הקוד לכך ניתן למצוא בחבילה com.baeldung.algorithms.primechecker על גיתוב.
