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

18/08/2010

טבלת מספרים ראשוניים בדרך איטרטיבית

Filed under: Uncategorized — תגיות: , , — גרי רשף @ 22:25

בפוסט זה הצעתי דרך לחישוב מספרים ראשוניים על ידי שליפה אחת (CTE רקורסיבי כפול – ליתר דיוק).
כאן אני מציע דרך איטרטיבית שהיא יותר יעילה, כשהרעיון באופן כללי הוא כזה:
כשבודקים אם מספר מסויים הוא ראשוני – יש לנסות ולחלק אותו בכל המספרים הראשוניים שהם קטנים או שווים לשורש הריבועי שלו (או בהיעדר טבלה של מספרים ראשוניים – וזה בדרך כלל המצב – מחלקים אותו בכל המספרים השלמים בין 2 לבין השורש הריבועי שלו).
ההיגיון כאן הוא די ברור – אם מספר מתחלק במספר הגדול מהשורש שלו – התוצאה תהיה קטנה מהשורש שלו, ממילא הוא מתחלק גם בה. למשל- 100 מתחלק ב-20 (הגדול מהשורש שלו שהוא 10) והתוצאה היא 5; ומכאן ש-100 מתחלק ב-5 שקטן מהשורש 10. לפיכך, כדי לבדוק ראשוניות של מספר, די לחלקו רק במספרים קטנים או שווים לשורש שלו.
כשיוצרים מספרים ראשוניים השיטה צריכה להיות דומה: אם נתונים לנו ארבעת המספרים הראשוניים הראשונים (2,3,5,7) נוכל לבדוק בעזרתם את ראשוניותם של כל המספרים מ-8 ועד image , מכיוון שאם הם אינם ראשונים – הם יתחלקו באחד מארבעת הראשונים הידועים. את מה שאחרי 63 כבר לא נוכל לבדוק, למשל 67 אינו מתחלק באף אחד מארבעת הנ"ל, אבל אולי הוא מתחלק במספר ראשוני שגדול מ-7 ושכרגע אינו ידוע לנו?

ב-ק-י-צ-ו-ר – ניצור טבלת מספרים מאונדקסת מ-1 ועד 1000000 (מיליון):

use tempdb;

Go


Declare @N Int=1000000;

With T As

(Select    1 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

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

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

Create Table T_Rishonim(N BigInt Unique Clustered);

Go

וכעת התהליך עצמו: נכניס לטבלת הראשוניים את 2 שהוא הראשוני הראשון, ובהמשך נרוץ בלולאה כל עוד מתווספים ראשוניים לטבלה, ובכל איטרציה נבדוק לגבי כל המספרים הרלוונטיים (החל מ N+1 וכלה ב image כאשר N הוא הראשוני הכי גדול עד כה) מי ראשוני, ולצורך כך אין צורך לחלק אותו בכל הראשוניים מ-2 ועד לשורש שלו, אלא עד לראשון שמחזיר שארית 0 ואז ברור שאינו ראשוני, ואם מוחזר Null סימן שהוא כן ראשוני:

Insert Into T_Rishonim Select 2;

Go


While @@RowCount>0

With T As

(Select    *,

        (Select MIN(R.N)

        From    T_Rishonim R

        Where    R.N<=SQRT(M.Mispar)

                And M.Mispar%R.N=0) Div

From    T_Misparim M

Inner Join (Select    Max(N) Mx

            From    T_Rishonim) R

            On M.Mispar Between R.Mx+1 And Power(R.Mx+1,2)-1)

Insert Into T_Rishonim

Select    Mispar

From    T

Where    Div Is Null;

Go

לי זה לקח כ-40 שניות, ואם יש דרך מהירה יותר – אשמח לשמוע.

לסיום – נעיין ברשימת הראשוניים להתפעל ממעשה ידינו:

Select    *

From    T_Rishonim

Order By 1;

Go

ולבסוף טיפ קטן שאינו קשור לנושא: ה-Execution Plan של השליפה הממויינת מטבלת המספרים הראשוניים זה בין אם יש מיון ובין אם אין, מכיוון שהמערכת בכל מקרה מבצעת Scan במעלה ה-Clustered Index ומחזירה סט ממויין גם אם לא התבקשה. זה צפוי להיות כך בכל מקרה בו שולפים סט מפולטר וממויין לפי ה-Clustered Index.

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

2 תגובות »

  1. […] זמן ריצה- 24 שניות, בהחלט לא רע בהתייחס לאלגוריתם אחר שניסיתי לאחרונה. Published Friday, August 27, 2010 10:41 PM על ידי גרי […]

    פינגבאק של הנפה של ארטוסתנס - גרי רשף — 19/01/2012 @ 19:23

  2. […] ריצה- 24 שניות, בהחלט לא רע בהתייחס לאלגוריתם אחר שניסיתי לאחרונה. […]

    פינגבאק של הנפה של ארטוסתנס « הבלוג של גרי רשף — 27/08/2010 @ 21:41


RSS feed for comments on this post. TrackBack URI

להשאיר תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s

בלוג בוורדפרס.קום.

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