> ## Content Index
> Fetch the complete content index at: https://informatic-ar.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# خوارزمية Sieve of Eratosthenes
- URL: https://informatic-ar.com/sieve_of_eratosthenes/
- Published: 2013-10-05T13:57:40.000Z
- Updated: 2026-10-03T22:31:54.000Z
- Author: أحمد عصام
- Tags: خوارزميات, algorithm, prime numbers, prime, خوارزمية, #wordpress-archive, #Import 2026-10-03 20:48

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

الخوارزمية من [wikipedia](http://en.wikipedia.org/wiki/Sieve%5Fof%5FEratosthenes?ref=informatic-ar.com)

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) :

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

[![eratosthenes-ex-0](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-0-300x300.png)](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-0.png)

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

[![eratosthenes-ex-1](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-1-300x300.png)](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-1.png)  
ملاحظة: اللون الاخضر يعني عدد أولي ، أما الأحمر فهو ليس أولي.

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

[![eratosthenes-ex-2](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-2-300x300.png)](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-2.png)

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

[![eratosthenes-ex-3](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-3-300x300.png)](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-3.png)

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

[![eratosthenes-ex-4](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-4-300x300.png)](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-4.png)

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

[![eratosthenes-ex-5](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-5-300x300.png)](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-5.png)

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

[![eratosthenes-ex-6](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-6-269x300.png)](https://informatic-ar.com/wp-content/uploads/2013/10/eratosthenes-ex-6.png)

مثال آخر :

[![Animation_Sieve_of_Eratosth-2-ca](https://informatic-ar.com/wp-content/uploads/2013/10/Animation_Sieve_of_Eratosth-2-ca-300x248.gif "الصورة متحركه قم بالضغط عليها لمشاهدتها")](https://informatic-ar.com/wp-content/uploads/2013/10/Animation%5FSieve%5Fof%5FEratosth-2-ca.gif) الصورة متحركه قم بالضغط عليها لمشاهدتها

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

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

```cpp
#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;
}
```

**شرح بسيط :**

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

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

array[1] = 0;
```

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

```cpp
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

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

```cpp
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](http://en.wikipedia.org/wiki/Sieve%5Fof%5FEratosthenes?ref=informatic-ar.com)  
[Prime\_number](http://en.wikipedia.org/wiki/Prime%5Fnumber?ref=informatic-ar.com)  
[Sieve\_of\_Eratosthenes](http://www.algolist.net/Algorithms/Number%5Ftheoretic/Sieve%5Fof%5FEratosthenes?ref=informatic-ar.com)  
كتاب Algorithms in C.

الكود بالمرفقات.  
[printprime.cpp.tar](https://informatic-ar.com/wp-content/uploads/2013/10/printprime.cpp%5F.tar.gz)