מה סיבוכיות הנפה של ארטוסתנס?

[gil levi]

מה סיבוכיות הנפה של ארטוסתנס?

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

 

[ron369]

אתה צריך אולי להעזר בנתון, שהתפלגות

המספרים הראשוניים בתחום [1,n] היא בקירוב: n/lgn, אסימפטוטית. עוזר?

(אם אני אגלה לך את התשובה, זה לא יהיה שווה הרבה הרי, נכון? בקירוב, בכל אופן, אני חושב שאני יודע)

 

[the new L]

אגב,

מה לגבי חסם אדוק אסימפטוטית לכמות הראשוניים בתחום [1,n]? (טוב נו, האמת שמתן חסם הדוק כזה פותרת את השערת רימן, הבעיה הפתוחה הגדולה ביותר במתמטיקה

)

 

[ron369]

n/lgn

 

[the new L]

זה לא הדוק