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

מספרים ראשוניים
למספר טבעי  (1,2,3,4,…)קוראים "ראשוני" אם הוא גדול מ-1 ואם המספרים הטבעיים היחידים שמחלקים אותו ללא שארית הם 1 והוא עצמו. שימו לב שהמספר 1 עצמו אינו ראשוני.

הדרך הכי פשוטה לדעת אם המספר n הוא ראשוני היא לנסות לחלק אותו בכל המספרים הקטנים ממנו. אם נמצא שהוא לא מתחלק באף מספר חוץ מעצמו ומ-1 נדע שהוא ראשוני. כלומר צריך לנסות לחלקn/2, n/3,  n/4,…,n/(n-1) , או בסך הכול n-2 תרגילים. בשיטה הזאת, אם נרצה למצוא את כל המספרים הראשוניים הקטנים למשל מ-30 נצטרך לחלק כל אחד מהם בכל המספרים הקטנים ממנו ולמצוא מי מהם מתחלק רק בעצמו וב-1. חישוב לא מסובך יגלה שנצטרך לבצע 406 תרגילים!

לאורך ההיסטוריה חיפשו מתמטיקאים שיטות (אלגוריתמים) למצוא בקלות רבה יותר מספרים ראשוניים, למשל את כל המספרים הראשוניים עד מספר נתון. אחד מהכלים האלה נקרא על שמו של איש האשכולות היווני ארטוסתנס, שחי במצרים בשנים 194-276 לפני הספירה.

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


נוצר על ידי Francesc באמצעות גיאוגברה

נניח שאנחנו רוצים למצוא את כל המספרים הראשוניים עד 30 (ביישומון תוכלו למצוא את כל המספרים הראשוניים עד 100). נצייר על לוח משבצות את כל המספרים הטבעיים עד 30 לפי הסדר, מהקטן לגדול.

5

4

3

2

1

10

9

8

7

6

15

14

13

12

11

20

19

18

17

16

25

24

23

22

21

30

29

28

27

26

 

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

כשנסיים נרצה לעשות אותו דבר מהמספר הבא בתור, כלומר 4, אך היות שהוא כבר נמחק (כי הוא נמצא במרחק של 2 משבצות מהמספר 2) נמשיך ישר למספר 5. כפי שבוודאי כבר ניחשתם, נקפוץ ממנו בדילוגים של חמש משבצות, ונמחק כל מספר שלא נמחק קודם בכל משבצת שעליה ננחת. כך נמשיך עד שנגיע למספר הקטן ביותר שגדול או שווה לשורש 30. היות ששורש 30 הוא בין 5 ל-6, נעצור כשנסיים את הקפיצות שאורכן חמש משבצות.

כעת מובטח לנו שכל המספרים שנותרו על הלוח פרט ל-1 הם כל המספרים הראשוניים עד 30. בדוגמה שלנו קיבלנו שהמספרים הראשוניים עד 30 הם 2, 3, 5, 7, 11, 13, 17, 19, 23 ו-29.

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

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

ה"טעות" השנייה היא שלא עברנו על כל המספרים אלא עצרנו בשורש המספר הגבוה ביותר בלוח. גם זה בסדר: אם המספר n מתחלק במספר m, זאת אומרת שיש מספר אחר k כך ש n=m*k. אבל אם גם m וגם k גדולים משורש n, זה לא ייתכן! אם כך, לפחות אחד מהם הוא לכל היותר שורש n. לכן, כדי לבדוק אם מספר הוא ראשוני די לבדוק האם הוא מתחלק במספרים קטנים או שווים לשורש שלו וגדולים מ-1.

שימו לב שכשאנחנו בודקים אלו מספרים מתחלקים ב-11 ביישומון איננו מגלים אף מספר חדש שלא נמחק כבר. די לבדוק עד 10, שהוא שורש 100.

חישוב מהיר
שימו לב שלצורך יישום השיטה אנחנו מבצעים במהירות הרבה מאוד תרגילי חשבון בלי לשים לב. כשאנחנו עוברים מ-3 ל-9 באמצעות שתי קפיצות באורך שלוש משבצות, למשל, אנחנו מחשבים בעצם את התרגיל 9=3+3+3. היופי בשיטה הוא שבאמצעות ההמחשה הגרפית בלוח אנחנו לא שמים לב לתרגילים, אלא מבצעים אותם באופן טבעי וללא מאמץ.

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

תרומותיו של ארטוסתנס למדע ולמתמטיקה לא הסתכמו כמובן רק בפיתוח השיטה שתיארנו. בין היתר הוא מדד את היקף כדור הארץ בצורה מתוחכמת למדי – אך על זה נספר אולי הזדמנות אחרת.

ארי שביב
הפקולטה למתמטיקה ומדעי המחשב
מכון ויצמן למדע



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

0 תגובות