Sieve of Eratosthenes

ננתח את הבעיה הבאה: נרצה להדפיס את כל המספרים הראשוניים בין 0 למספר כלשהו N.

פתרון נאיבי

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

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

#include <stdbool.h>
bool is_prime(int n) {
    if (n < 0) {
        n = -n;
    }
    if (n <= 1) {
        // 0 and 1 are not prime
        return false;
    }
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

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

#include <stdbool.h>
#include <stdio.h>
bool is_prime(int n);
void print_primes(int max) {
    for (int i = 0; i < max; i++) {
        if (is_prime(i)) {
            printf("%d is prime\n", i);
        }
    }
}

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

לדוגמא, נניח שנרצה להדפיס את כל הראשוניים בין 0 ל-100. לאחר שגילינו כי 2 הוא מספר ראשוני, אנחנו יודעים כי כל כפולה שלו אינה ראשונית! כלומר, אין צורך לבדוק בכלל את 4, 6, 8 וכך הלאה עד ל-100. בצורה דומה, לאחר שגילינו כי 3 הוא מספר ראשוני, ניתן לפסול ללא בדיקה את 6, 9, 12 וכך הלאה עד ל-99.

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

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

קיים אלגוריתם עתיק בשם ה-Sieve of Eratosthenes, שפותר את הבעיה בצורה יעילה. האלגוריתם פועל לפי השלבים הבאים:

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

בתרגום לקוד, התוכנית שלנו תראה כך:

1. נייצר מערך של משתנים שגודלו N + 1- איבר במערך עבור כל המספרים מ-0 ועד N, כולל (לכן N + 1 ולא N).
2. מעניין אותנו רק האם האיבר באינדקס מסוים ראשוני או לא ולא מה ערכו, ולכן המערך יהיה מסוג bool.
3. מכיוון שהאלגוריתם פוסל מספרים ראשונים, נאתחל את כל המערך להיות true.

#include <stdbool.h>
#include <stdio.h>
#define N 1000
void sieve(void) {
    bool is_prime[N + 1];
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i <= N + 1; i++) {
        is_prime[i] = true;
    }
    for (int p = 2; p * p <= N; p++) {
        if (!is_prime[p]) {
            continue;
        }
        for (int i = p; i <= N / p; i++) {
            is_prime[i * p] = false;
        }
    }
    printf("Primes between 0 and %d are:\n", N);
    for (int i = 0; i < N; i++) {
        if (is_prime[i]) {
            printf("%d\n", i);
        }
    }
}