הבלוג של גרי רשף

27/08/2010

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

Filed under: Uncategorized — תגיות: , , , — גרי רשף @ 21:41

הנפה של ארסטותנס היא אלגוריתם למציאת כל המספרים הראשוניים מ-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 שניות, בהחלט לא רע בהתייחס לאלגוריתם אחר שניסיתי לאחרונה.

מודעות פרסומת

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

להשאיר תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

יצירה של אתר חינמי או בלוג ב־WordPress.com.

%d בלוגרים אהבו את זה: