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

יום רביעי, אוגוסט 18, 2010

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

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

יום רביעי, ינואר 13, 2010

לא הכי שימושי, אבל אתגר נצחי לחובבי הז'אנר: 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 ועד שורש המספר - מטעמי יעילות). ולבסוף- הדרך הכי...
אין תגובות