הנפה של אטקין

בתורת המספרים, הנפה של אטקין היא אלגוריתם מודרני למציאת כל המספרים הראשוניים עד למספר שלם שצוין. בהשוואה לנפה של ארטוסתנס, המסמנת כפולות ראשוניים, הנפה של אטקין עושה עבודה מקדימה ולאחר מכן מסמנת כפולות של ריבועים ראשוניים, ובכך משיגה מורכבות אסימפטוטית תאורטית טובה יותר. האלגוריתם נוצר בשנת 2003 על ידי ארתור אטקין ודניאל ג'יי ברנשטיין.

אלגוריתם

באלגוריתם:

• כל השאריות הן שאריות מודולו - שישים (חילוק המספר ב-60 והחזרת השארית).
• כל המספרים, כולל x ו - y, הם מספרים שלמים חיוביים.
• "היפוך ערך" ברשימת הנפה משמעו שינוי הסימון (ראשוני או לא ראשוני) לסימון ההפוך.
• פעולות אלו מובילות לכך שמספרים עם מספר אי-זוגי של פתרונות למשוואה המתאימה עשויים להיות ראשוניים (אם הם גם חסרי ריבועים), ומספרים עם מספר זוגי של פתרונות הם מספרים מרוכבים.

אתחול

1. יצירת רשימת תוצאות, הכנסת המספרים הראשוניים הקטנים 2, 3 ו-5 לתוך הרשימה.
2. יצירת רשימת נפה המכילה תא לכל מספר שלם חיובי. כל התאים ברשימה מסומנים תחילה כלא-ראשוניים.

לולאה ראשית

עבור כל ערך n ברשימת הנפה, נחלק את n c=ב-60 ואת השארית נסמן ב-r:

• אם r שווה ל-1, 13, 17, 29, 37, 41, 49 או 53, הפוך את הסימון עבור כל פתרון אפשרי למשוואה 4x² + y² = n.
• אם r שווה ל-7, 19, 31 או 43, הפוך את הסימון עבור כל פתרון אפשרי למשוואה 3x² + y² = n.
• אם r שווה ל־11, 23, 47 או 59, הפוך את הסימון עבור כל פתרון אפשרי למשוואה 3x² - y² = n כאשר x > y.
• אם r שווה לכל ערך אחר, התעלם ממנו לחלוטין.

לולאה פנימית

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

תיאור זה מספק סקירה כללית של האלגוריתם ולא את היישום המלא שלו.

הסבר

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

לכל המספרים n עם מודולו 60 השארית 1, 13, 17, 29, 37, 41, 49 או 53 יש שארית מודולו 4 של 1. המספרים הללו הם ראשוניים אם ורק אם מספר הפתרונות ל 4x² + y² = n הוא אי זוגי והמספר הוא ללא ריבוע.

לכל המספרים n עם מודולו 60 שארית 7, 19, 31 או 43 יש שארית מודולו 6 של 1. המספרים הללו הם ראשוניים אם ורק אם מספר הפתרונות ל 3x² + y² = n הוא אי זוגי והמספר לא מתחלק במספר ריבועי.

לכל המספרים n עם מודולו 60 שארית 11, 23, 47 או 59 יש מודולו 12 שארית של 11. המספרים הללו הם ראשוניים אם ורק אם מספר הפתרונות ל 3x² - y² = n הוא אי זוגי והמספר לא מתחלק במספר ריבועי.

אף אחד מהראשוניים הפוטנציאליים אינו מתחלק ב-2, 3 או 5, כך שהם לא ניתנים לחלוקה בריבועים שלהם. זו הסיבה שבדיקות חלוקה במספרים ריבועיים לא כוללות 2 ², 3 ² ו-5 ².

ראו גם

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