streamalism.org

1. הקדמה

במדריך זה נציג דרכים שונות בהן אנו יכולים ליצור מספרים ראשוניים באמצעות Java.

אם אתה מחפש לבדוק אם מספר הוא ראשוני - הנה מדריך מהיר כיצד לעשות זאת.

2. מספרים ראשוניים

נתחיל בהגדרת הליבה. מספר ראשוני הוא מספר טבעי הגדול מזה שאין לו מחלקים חיוביים מלבד אחד עצמו.

לדוגמה, 7 הוא ראשוני מכיוון ש -1 ו- 7 הם הגורמים השלמים החיוביים היחידים שלו, ואילו 12 אינו בגלל שיש לו את המחלקים 3 ו -2 בנוסף ל -1, 4 ו -6.

3. יצירת מספרים ראשוניים

בחלק זה נראה כיצד נוכל ליצור מספרים ראשוניים ביעילות הנמוכים מערך נתון.

3.1. ג'אווה 7 ולפני - כוח הברוט

רשימת סטטי ציבורי primeNumbersBruteForce (int n) {List primeNumbers = LinkedList חדש (); עבור (int i = 2; i <= n; i ++) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} להחזיר מספרים ראשוניים; } בוליאני סטטי ציבורי isPrimeBruteForce (int number) {for (int i = 2; i <number; i ++) {if (number% i == 0) {return false; }} להחזיר אמת; } 

כפי שאתה יכול לראות, primeNumbersBruteForce הוא חוזר על המספרים מ -2 עד נ ופשוט קורא ל isPrimeBruteForce () שיטה לבדוק אם מספר הוא ראשוני או לא.

השיטה בודקת את חלוקת המספרים לפי המספרים בטווח שבין 2 עד מספר 1.

אם בשלב כלשהו אנו נתקלים במספר הניתן לחלוקה, אנו מחזירים שקר. בסוף כשאנחנו מוצאים שהמספר אינו מתחלק באף אחד מהמספרים הקודמים שלו, אנו מחזירים נכון ומציין שהוא מספר ראשוני.

3.2. יעילות ואופטימיזציה

האלגוריתם הקודם אינו לינארי ויש לו את מורכבות הזמן של O (n ^ 2). האלגוריתם גם לא יעיל ויש בבירור מקום לשיפור.

בואו נסתכל על המצב ב isPrimeBruteForce () שיטה.

כאשר מספר אינו ראשוני, ניתן לחשב מספר זה לשני גורמים, כלומר א ו ב כְּלוֹמַר מספר = a * ב. אם שניהם א ו ב היו גדולים יותר מהשורש הריבועי של נ, a * ב יהיה גדול מ נ.

אז לפחות אחד מאותם גורמים חייב להיות קטן או שווה לשורש הריבועי של המספר וכדי לבדוק אם המספר הוא ראשוני, עלינו לבדוק רק גורמים הנמוכים או שווים לשורש הריבוע של המספר הנבדק.

מספרים ראשוניים לעולם אינם יכולים להיות מספר זוגי מכיוון שכולם מספרים זוגיים מתחלקים ב -2.

בנוסף, מספרים ראשוניים לעולם אינם יכולים להיות מספר זוגי שכן מספרים זוגיים מתחלקים ב -2.

בהתחשב ברעיונות הנ"ל, בואו נשפר את האלגוריתם:

רשימת סטטי ציבורי primeNumbersBruteForce (int n) {List primeNumbers = LinkedList חדש (); אם (n> = 2) {primeNumbers.add (2); } עבור (int i = 3; i <= n; i + = 2) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} להחזיר מספרים ראשוניים; } בוליאני סטטי פרטי isPrimeBruteForce (int מספר) {for (int i = 2; i * i <number; i ++) {if (number% i == 0) {return false; }} להחזיר אמת; } 

3.3. באמצעות Java 8

בואו נראה כיצד נוכל לשכתב את הפיתרון הקודם באמצעות ניבים של Java 8:

רשימה סטטית ציבורית primeNumbersTill (int n) {return IntStream.rangeClosed (2, n) .filter (x -> isPrime (x)). boxed () .collect (Collectors.toList ()); } בוליאני סטטי פרטי isPrime (int מספר) {return IntStream.rangeClosed (2, (int) (Math.sqrt (number))). filter (n -> (n & 0X1)! = 0). allMatch (n -> x% n! = 0); } 

3.4. שימוש במסננת של ארטוסטנס

יש עוד שיטה יעילה שיכולה לעזור לנו ליצור מספרים ראשוניים ביעילות, והיא נקראת מסננת של ארטוסטנס. יעילות הזמן שלו היא O (n logn).

בואו נסתכל על השלבים של האלגוריתם הזה:

1. צור רשימה של מספרים שלמים עוקבים מ -2 עד נ: (2, 3, 4, ..., n)
2. בתחילה, תן עמ ' להיות שווה 2, המספר הראשוני הראשון
3. התחיל מ עמ ', ספרו במרווחים של עמ ' וסמן כל אחד מהמספרים הללו גדול מ- עמ ' עצמה ברשימה. מספרים אלה יהיו 2p, 3p, 4p וכו '; שימו לב שאולי חלקם כבר סומנו
4. מצא את המספר הראשון גדול מ- עמ ' ברשימה שאינה מסומנת. אם לא היה מספר כזה, עצור. אחרת, תן עמ ' עכשיו שווה למספר זה (שהוא הפריים פריים הבא), וחזור משלב 3

בסוף כאשר האלגוריתם מסתיים, כל המספרים ברשימה שאינם מסומנים הם המספרים הראשוניים.

כך נראה הקוד:

רשימה סטטית ציבורית sieveOfEratosthenes (int n) {בוליאני ראשוני [] = בוליאני חדש [n + 1]; Arrays.fill (ראשוני, נכון); עבור (int p = 2; p * p <= n; p ++) {if (prime [p]) {for (int i = p * 2; i <= n; i + = p) {prime [i] = שֶׁקֶר; }}} רשום primeNumbers = חדש LinkedList (); עבור (int i = 2; i <= n; i ++) {if (prime [i]) {primeNumbers.add (i); }} להחזיר מספרים ראשוניים; } 

3.5. דוגמה לעבודה של מסננת ארטוסטנס

בואו נראה איך זה עובד עבור n = 30.

שקול את התמונה לעיל, הנה המעברים שבוצעו על ידי האלגוריתם:

1. הלולאה מתחילה ב- 2, אז אנו משאירים 2 ללא סימון ומסמנים את כל המחלקים של 2. זה מסומן בתמונה בצבע האדום
2. הלולאה עוברת ל -3, ולכן אנו משאירים 3 לא מסומנים ומסמנים את כל המחלקים של 3 שטרם מסומנים. זה מסומן בתמונה בצבע הירוק
3. לולאה עוברת ל -4, זה כבר מסומן, אז אנחנו ממשיכים
4. לולאה עוברת ל -5, אז אנחנו משאירים 5 לא מסומנים ומסמנים את כל המחלקים של 5 שעדיין לא מסומנים. זה מסומן בתמונה בצבע הסגול
5. אנו ממשיכים מעל המדרגות עד שמגיעים ללולאה השווה לשורש הריבועי של נ

4. מסקנה

במדריך מהיר זה, המחשנו דרכים בהן אנו יכולים ליצור מספרים ראשוניים עד ערך 'N'.

ניתן למצוא את היישום של דוגמאות אלה ב- GitHub.