خوارزمية Sieve of Eratosthenes

تعتبر خوارزمية Sieve of Eratosthenes من أسهل الخوارزميات لإيجاد الأعداد الأولية Prime Numbers ضمن مجال معين من الأعداد الصحيحة n ، حيث تقوم فكرتها على حذف مضاعفات الأعداد داخل هذا المجال ، حيث أن تعريف الأعداد الأولية يستبعد وجود الأعداد التي يمكن إيجادها كحاصل ضرب عددين.

الخوارزمية من wikipedia

1. Create a list of consecutive integers from two to n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Strike from the list all multiples of p greater than p.
4. Find the first number remaining on the list greater than p (this number is the next prime); let p equal this number.
5. Repeat steps 3 and 4 until p^2 is greater than n.
6. All the remaining numbers on the list are prime.

سنوضح الخوارزمية عبر مثال بسيط لإيجاد الأعداد الأولية من 1 إلى 100.
(ملاحظة: العدد 1 لا يعتبر عدد أولي حيث أنه لا يوجد عددين مختلفين يقسما العدد 1) :

في البداية سننشئ مصفوفة من الأعداد :

سنبدأ من العدد الأولي 2 ، وسنقوم بإزالة كل مضاعفاته ابتداءا من 4 :

ملاحظة: اللون الاخضر يعني عدد أولي ، أما الأحمر فهو ليس أولي.

العدد 3 هو أولي ، وسنحذف كل مضاعفاته ابتداءا من 9 :

نفس الفكرة مع العدد 5 :

وكذلك العدد 7:

العدد التالي الآن هو 11 ، لكن سنتوقف هنا لأن مربع العدد 11 أكبر من المجال المطلوب 100.

إذاً الأعداد الأولية من 1 إلى 100 هي :

مثال آخر :

الصورة متحركه قم بالضغط عليها لمشاهدتها

تطبيق الخوارزمية :

هذا تطبيق بسيط للخوارزمية باستخدام سي++ ، والفكرة مشابهة تماما للمثال في الأعلى حيث سأنشئ مصفوفة من 100 عنصر ، وسأضع جميع القيم فيها مساوية للواحد دلالة على أن كل العناصر هي أولية ، وبعدها عندما نجد عدد مركب Composite number وليكن i سنجعل قيمة العنصر i هي الصفر دلالة على أنه تم حذف العنصر.

#include 
#include 
#include 

using namespace std;

void sieveOfEratosthenes(int N)
{
    int* array = new int[N+1];

    for (int i=2;i<=N;++i)
   array[i] = 1;

    array[1] = 0;

    for (int i=2;i<=sqrt(N);++i) {
   if (array[i] == 0)
       continue;
   for (int j=i*i;j<=N;j+=i) {
       array[j] = 0;
   }
    }

    for (int i=2;i<=N;++i)
   if (array[i])
       cout << i << " " ;

    cout << endl;
    delete [] array;
}

int main(int argc,char* argv[])
{
    if (argc == 2)
   sieveOfEratosthenes(atoi(argv[1]));
    else
   sieveOfEratosthenes(100);

    return 0;
}

شرح بسيط :

    int* array = new int[N+1];

    for (int i=2;i<=N;++i)
   array[i] = 1;

    array[1] = 0;

هنا تم انشاء المصفوفة وتعيين القيمة 1 لكل الأعداد دلالة على أنها أولية ، أما العدد 1 فتم تعيين القيمة 0 له دلالة على أنه ليس عدد أولي.

    for (int i=2;i<=sqrt(N);++i) {
   if (array[i] == 0)
       continue;
   for (int j=i*i;j<=N;j+=i) {
       array[j] = 0;
   }
    }

لا يوجد داعي لأن نمر على جميع الأعداد من 1 الى 100 ! سنبدأ من العدد 2 لأن العدد 1 قد ذكرنا بأنه ليس أولي ، وسننتهي عند العدد 10 (تأتي من تطبيق الجذر التربيعي على n) لأنه عنما تعمل الخوارزمية على العدد 2 و 3 و 5 و 7 و9 ستجد أننا قد مررنا على كل الأعداد (المضاعفة) في هذا المجال.

في البداية سيتم اختبار هل العدد ليس أولي ؟ إذا كانت الاجابة لا فهذا يعني أن العدد أولي ويجب معرفة مضاعفاته لكي نقوم بازالتها .
أما إذا كانت الإجابة نعم فهذا يعني أن هذا العدد مضاعف Composite number وبالتأكيد مضاعفات هذا العدد هي ليس أولية وقد تم ازالتها من قبل.

نتيجة البرنامج :
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

وهذا تطبيق آخر للدالة :

void sieveOfEratosthenes(int N)
{
    int* array = new int[N+1];

    for (int i=2;i<=N;++i)
   array[i] = 1;

    array[1] = 0;

    for (int i=2;i<=N/2;++i)
   for (int j=2;j<=N/i;++j) {
       cout << i*j << endl;
       array[i*j] = 0;
   }

    for (int i=2;i<=N;++i)
   if (array[i])
       cout << i << " " ;

    cout << endl;    
    delete [] array;
}

مصادر:
Wikipedia
Prime_number
Sieve_of_Eratosthenes
كتاب Algorithms in C.

الكود بالمرفقات.
printprime.cpp.tar