בעיה בתרגיל בשפת JAVA

[דניאל נ]

שלום אני צריך עזרה עם תרגיל שיחשב את המספרים הראשוניים בין 1 ל-n ומדפיסה אותם.

חשבתי על זה הרבה ולא הצלחתי למצוא את הפתרון

תודה לעוזרים

[שניצל]

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

איך בודקים אם מספר הוא ראשוני? הדרך הכי פשוטה כמובן היא לעבור על כל המספרים שקטנים ממנו (לא כולל 1, כמובן) ולבדוק אם הוא מתחלק באחד מהם.

כמובן יש דרכים יותר חכמות/יעיליות, אבל זה הבסיס.

[matteo]

התשובה לשאלתך היא "הנפה של ארטוסתנס"

[דניאל נ]

תודה רבה !!!!!!

[dj_tg]

הנה הפתרון

public boolean isPrime(int number) {

if (number == 1)

return false;

if (number == 2)

return true;

if (number % 2 == 0)

return false;

for (int d = 3; d <= (int) Math.sqrt(number); d++)

if (number % d == 0)

return false;

return true;

}

והנה ההסבר :

http://www.algolist.net/Algorithms/Number_theoretic_algorithms/Primality_test_%28naive%29

[שניצל]

dj_tg, ערוך בבקשה את ההודעה שלך ושים את הקוד בטג קוד (כפתור ה-# שליד כפתור הציטוט) כדי שיראה נורמלי.

חוץ מזה, אני תוהה - למה אתה טורח במיוחד לבדוק את החלוקה ב-2 בנפרד משאר המספרים? ה-if השני והשלישי פשוט מיותרים (וכמובן את הלולאה צריך להתחיל מ-2 במקום מ-3).

[Armageddon26]

אם אתם מתחילים לרוץ רק עד השורש וכו' אז עדיף כבר לייעל את זה עוד יותר.

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

אם תרצה הסבר למה זה עובד אז תגיד.

[שניצל]

זה נקרא הנפה של ארטוסתנס, ו-matteo כבר ציין את זה.

[Zelig]

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

אישית, אני חושב שזה ממש מוצלח בשביל יווני שחי לפני 2200 שנה

[Armageddon26]

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

[etal]

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

[Armageddon26]

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

[Zelig]

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

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