הנפה של ארטוסתנס

27/08/2010

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

נכין טבלת מספרים מאונדקסת מ-2 ועד 1,000,000:

If Object_Id('T_Misparim') Is Not Null Drop Table T_Misparim;

Go


Declare @N Int=1000000;

With T As

(Select    2 Mispar

Union All

Select    Mispar+1

From    T

Where    Mispar<@N)

Select    *

Into    T_Misparim

From    T

option (MaxRecursion 0);

Go


Create Unique Clustered Index Idx_T_Misparim On T_Misparim(Mispar);

Go

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

ונמחק מהטבלה את כל המספרים הגדולים ממנו המתחלקים בו:

Declare    @N Int,

        @Mx Int;

Select    @N=MIN(Mispar),

        @Mx=Sqrt(Max(Mispar))

From    T_Misparim;

While    @N<=@Mx

    Begin

    Delete

    From    T_Misparim

    Where    Mispar>@N

            And Mispar%@N=0;

    Select    @N=MIN(Mispar)

    From    T_Misparim

    Where    Mispar>@N;

    End;

Go

זמן ריצה- 24 שניות, בהחלט לא רע בהתייחס לאלגוריתם אחר שניסיתי לאחרונה.

הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *