פורסם 2009 בספטמבר 1016 שנים שלום אני צריך עזרה עם תרגיל שיחשב את המספרים הראשוניים בין 1 ל-n ומדפיסה אותם.חשבתי על זה הרבה ולא הצלחתי למצוא את הפתרון תודה לעוזרים
פורסם 2009 בספטמבר 1016 שנים כתוב פונקציה שבודקת אם מספר מסוים הוא ראשוני, ואז תעבור על כל המספרים מ-1 עד n ותריץ עבור כל אחד מהם את הפונקציה.איך בודקים אם מספר הוא ראשוני? הדרך הכי פשוטה כמובן היא לעבור על כל המספרים שקטנים ממנו (לא כולל 1, כמובן) ולבדוק אם הוא מתחלק באחד מהם.כמובן יש דרכים יותר חכמות/יעיליות, אבל זה הבסיס.
פורסם 2009 בספטמבר 1216 שנים הנה הפתרון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
פורסם 2009 בספטמבר 1216 שנים dj_tg, ערוך בבקשה את ההודעה שלך ושים את הקוד בטג קוד (כפתור ה-# שליד כפתור הציטוט) כדי שיראה נורמלי.חוץ מזה, אני תוהה - למה אתה טורח במיוחד לבדוק את החלוקה ב-2 בנפרד משאר המספרים? ה-if השני והשלישי פשוט מיותרים (וכמובן את הלולאה צריך להתחיל מ-2 במקום מ-3).
פורסם 2009 בספטמבר 1216 שנים אם אתם מתחילים לרוץ רק עד השורש וכו' אז עדיף כבר לייעל את זה עוד יותר.תיצור רשימה (ממוינת) של מספרים ראשוניים שכבר מצאת ובמקום לבדוק אם מספר לא מתחלק בכל המספרים עד השורש שלו תבדוק את כל הראשוניים שמצאת שקטנים או שווים לשורש. עוד ייעול זה לרוץ רק על אי-זוגיים (וכמובן להכליל את 2 בראשוניים).אם תרצה הסבר למה זה עובד אז תגיד.
פורסם 2009 בספטמבר 1316 שנים מעניין לציין שהנפה של ארטוסתנס היא אלגוריתם הרבה יותר יותר יעיל מהאלגוריתם הנאיבי של נסיון חלוקה של כל המספרים, מבחינת ביצועים. הוא נחשב ליעיל למדי למציאת המספרים הראשוניים עד כמה מיליונים (וזאת כיוון שמספר הפעולות שהוא מבצע עבור כל מספר i הוא מספר הגורמים היחודיים של i), והאמת היא שהוא גם לא רע אח"כ. אישית, אני חושב שזה ממש מוצלח בשביל יווני שחי לפני 2200 שנה
פורסם 2009 בספטמבר 1316 שנים מה שאני אמרתי זאת לא הנפה של ארטוסתנס. זה יותר דומה לשיטה הנאיבית רק מייעל אותה. אני למשל צריך כמות זיכרון ככמות הראשוניים שאמצא. בשיטת הנפה של ארטוסתנס צריך כמות זיכרון לינארית למספר שעד אליו אתה רוצה למצוא ראשוניים. מבחינת יעילות זמן ריצה אני לא יודע מה עדיף.
פורסם 2009 בספטמבר 1316 שנים אם רוצים לבדוק ראשוניות בצורה יעילה אז משתמשים באלגוריתם מילר-רבין (הסבר יותר טוב כאן), לא שזה באמת רלוונטי לשאלה המקורית.
פורסם 2009 בספטמבר 1316 שנים זה באמת לא כל כך רלוונטי כי אנחנו מדברים על מציאת כל הראשוניים עד מספר מסוים ולא לבדוק מספר בודד.
פורסם 2009 בספטמבר 1316 שנים מה שאני אמרתי זאת לא הנפה של ארטוסתנס. זה יותר דומה לשיטה הנאיבית רק מייעל אותה. אני למשל צריך כמות זיכרון ככמות הראשוניים שאמצא. בשיטת הנפה של ארטוסתנס צריך כמות זיכרון לינארית למספר שעד אליו אתה רוצה למצוא ראשוניים. מבחינת יעילות זמן ריצה אני לא יודע מה עדיף.מסתבר גם שיש וריאציות על הנפה של ארטוסתנססטסטס שתופסות הרבה פחות זכרון. אבל כמובן, שיטות מודרניות שמבוססות על תורת המספרים ושאר ירקות מנצחות.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.