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

13/01/2010

מחולל מספרים ראשוניים

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

לא הכי שימושי, אבל אתגר נצחי לחובבי הז'אנר:

Declare @N Int=1000;
With T As
(Select 1 Mispar
Union All
Select Mispar+1
From T
Where Mispar<@N)
Select T1.Mispar*T2.Mispar Mispar
From T T1,
T T2
Group By T1.Mispar*T2.Mispar
Having Count(*)=2
And T1.Mispar*T2.Mispar<=@N
Order By 1
option (MaxRecursion 0);

במקרה זה מוכפלים המספרים 1..1000 אלו באלו,
ונשלפות המכפלות שמופיעות רק פעמיים:
אלו הם המספרים הראשונים שנוצרים רק ממכפלה ב-1.

ודרך שונה:

Declare @N Int=1000;
With T As
(Select 2 Mispar
Union All
Select Mispar+1
From T
Where Mispar<@N)
Select Mispar
From T T1
Where Not Exists (Select *
From T T2
Where T2.Mispar<=Sqrt(T1.Mispar)
And T1.Mispar%T2.Mispar=0)
Order By 1
option (MaxRecursion 0);

במקרה זה מחפשים את כל המספרים מ-2 ואילך שאין מספר אחר שהם מתחלקים בו ללא שארית (נבדקים כל המספרים מ-2 ועד שורש המספר – מטעמי יעילות).

ולבסוף- הדרך הכי יעילה שמצאתי: קצת דומה לראשונה אבל היישום שונה.
יוצרים על ידי ה-CTE הרקורסיבי את המספרים מ-2 עד 1000 (1 קצת מיותר..),
יוצרים CTE רקורסיבי נוסף שעבור כל אחד מהמספרים של הקודם- יוצר את כל המכפלות שלו עד 1000,
ולבסוף בודקים איזה מספר הופיע רק פעם אחת:

Declare @N Int=1000;
With T As
(Select 2 Mispar
Union All
Select Mispar+1
From T
Where Mispar<@N),
Tdpl As
(Select Mispar Mispar,
Mispar MisparDpl
From T
Union All
Select Mispar,
MisparDpl+Mispar
From Tdpl
Where MisparDpl<=@N)
Select MisparDpl
From Tdpl
Where MisparDpl<=@N
Group By MisparDpl
Having Count(*)=1
Order By 1
option (MaxRecursion 0);

בשני המקרים ניתן להריץ עד מספר אחר (במקום עד 1000) על ידי שינוי ערכו של N@.

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

תגובה אחת »

  1. […] — תגים:Mathematics, Prime Numbers, SQL Server — גרי רשף @ 22:25 בפוסט זה הצעתי דרך לחישוב מספרים ראשוניים על ידי שליפה אחת (CTE […]

    פינגבאק של טבלת מספרים ראשוניים בדרך איטרטיבית « הבלוג של גרי רשף — 18/08/2010 @ 22:31


RSS feed for comments on this post. TrackBack URI

להשאיר תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s

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

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