غربال إراتوستينس

في الرياضيات ، غربال إراتوستينس هو خوارزمية قديمة لإيجاد جميع الأعداد الأولية حتى أي حد معين.

يتم ذلك عن طريق تصنيف مضاعفات كل عدد أولي، بدءًا من العدد الأولي الأول، وهو 2، بشكل متكرر على أنها أعداد مركبة (أي غير أولية). تُولّد مضاعفات أي عدد أولي كسلسلة من الأعداد تبدأ من ذلك العدد، بفارق ثابت بينها يساوي ذلك العدد الأولي. ^{[ 1 ]} هذا هو الفرق الأساسي بين الغربال واستخدام القسمة التجريبية لاختبار قابلية كل عدد مرشح للقسمة على كل عدد أولي. ^{[ 2 ]} بمجرد تصنيف جميع مضاعفات كل عدد أولي مكتشف على أنها أعداد مركبة، تصبح الأعداد المتبقية غير المصنفة أعدادًا أولية.

أقدم إشارة معروفة للمنخل ( اليونانية القديمة : κόσκινον Ἐρατοσθένους ، kóskinon Eratosthénous ) موجودة في مقدمة نيكوماخوس الجراسي في الحساب ، ^{[ 3 ]} وهو كتاب من أوائل القرن الثاني الميلادي ينسبه إلى إراتوستينس القيرواني ، وهو كتاب من القرن الثالث قبل الميلاد. عالم رياضيات يوناني ، على الرغم من وصف الغربلة بالأرقام الفردية بدلاً من الأعداد الأولية. ^{[ 4 ]}

يُعدّ هذا الأسلوب أحد أساليب غربلة الأعداد الأولية ، وهو من أكثر الطرق فعاليةً لإيجاد جميع الأعداد الأولية الأصغر. ويمكن استخدامه لإيجاد الأعداد الأولية في المتتابعات الحسابية . ^{[ 5 ]}

ملخص

غربل الاثنينات وغربل الثلاثةات: غربال إراتوستينس. عندما تسمو المضاعفات، تكون الأعداد المتبقية أعدادًا أولية.

— مجهول ^{[ 6 ]}

العدد الأولي هو عدد طبيعي له قاسمان طبيعيان مختلفان تمامًا : العدد 1 ونفسه.

لإيجاد جميع الأعداد الأولية الأقل من أو تساوي عددًا صحيحًا معينًا $n$ باستخدام طريقة إراتوستينس:

أنشئ قائمة من الأعداد الصحيحة المتتالية من 2 إلى $n$ : $(2, 3, 4, ..., n)$ .
في البداية، لنفترض أن $p$ يساوي 2، وهو أصغر عدد أولي.
قم بترقيم مضاعفات $p$ عن طريق العد بزيادات $p$ من $2p$ إلى $n$ $،$ وقم بوضع علامة عليها في القائمة (ستكون هذه $2p ، 3p ، 4p ، ...$ ؛ لا ينبغي وضع علامة على $p نفسه).$
ابحث عن أصغر عدد في القائمة أكبر من $p$ وغير مُعلَّم. إذا لم يكن هناك عدد كهذا، فتوقف. وإلا، فاجعل $p$ يساوي هذا العدد الجديد (وهو العدد الأولي التالي)، وكرر العملية من الخطوة 3.
عندما تنتهي الخوارزمية، فإن الأرقام المتبقية غير المحددة في القائمة هي جميع الأعداد الأولية الأقل من $n$ .

الفكرة الأساسية هنا هي أن كل قيمة تُعطى لـ $p$ ستكون عددًا أوليًا، لأنه لو كان عددًا مركبًا لكانت ستُصنّف كمضاعف لعدد أولي أصغر منه. لاحظ أن بعض الأعداد قد تُصنّف أكثر من مرة (مثلًا، 15 ستُصنّف لكل من 3 و5).

الخاصية الأساسية للمنخل هي أنه لا حاجة إلا لعمليات الجمع، ولا يتم استخدام عمليات الضرب أو القسمة.

كتحسين، يكفي وضع علامات على الأرقام في الخطوة 3 بدءًا من $p 2$ ، حيث ستكون جميع مضاعفات $p$ الأصغر قد وُضعت عليها علامات بالفعل عند تلك النقطة. هذا يعني أنه يُسمح للخوارزمية بالتوقف في الخطوة 4 عندما يكون $p 2$ أكبر من $n$ . ^{[ 1 ]}

يتمثل أحد التحسينات الأخرى في إدراج الأعداد الفردية فقط في البداية، $(3، 5، ...، ن)$ ، ثم العد بزيادات قدرها $2p$ $في$ الخطوة 3، وبالتالي تحديد مضاعفات $p$ الفردية فقط . يظهر هذا بالفعل في الخوارزمية الأصلية. ^{[ 1 ]}^{[ 4 ]} يمكن تعميم هذا باستخدام تحليل العجلة ، بتكوين القائمة الأولية من الأعداد الأولية فيما بينها مع الأعداد الأولية القليلة الأولى فقط، وليس فقط من الأعداد الفردية (أي الأعداد الأولية فيما بينها مع 2)، والعد بزيادات معدلة وفقًا لذلك بحيث يتم توليد مضاعفات $p$ الأولية فيما بينها مع تلك الأعداد الأولية الصغيرة فقط. ^{[ 7 ]}

مثال

لإيجاد جميع الأعداد الأولية الأقل من أو تساوي 30، اتبع الخطوات التالية.

أولاً، قم بإنشاء قائمة بالأعداد الطبيعية من 2 إلى 30:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

الرقم الأول في القائمة هو 2؛ اشطب كل رقم ثانٍ في القائمة بعد الرقم 2 عن طريق العد تصاعديًا من 2 بزيادات قدرها 2 (ستكون هذه جميع مضاعفات الرقم 2 في القائمة):

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

الرقم التالي في القائمة بعد الرقم 2 هو 3؛ اشطب كل رقم ثالث في القائمة بعد الرقم 3 عن طريق العد تصاعديًا من 3 بزيادات قدرها 3 (ستكون هذه جميع مضاعفات الرقم 3 في القائمة):

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

الرقم التالي الذي لم يتم شطبه بعد في القائمة بعد الرقم 3 هو 5؛ اشطب كل رقم خامس في القائمة بعد الرقم 5 عن طريق العد تصاعديًا من 5 بمضاعفات 5 (أي جميع مضاعفات الرقم 5):

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

الرقم التالي الذي لم يُشطب بعد في القائمة بعد الرقم 5 هو 7؛ والخطوة التالية هي شطب كل رقم سابع في القائمة بعد الرقم 7، ولكنها جميعًا مشطوبة بالفعل في هذه المرحلة، لأن هذه الأرقام (14، 21، 28) هي أيضًا مضاعفات لأعداد أولية أصغر لأن 7 × 7 أكبر من 30. الأرقام التي لم تُشطب في هذه المرحلة من القائمة هي جميع الأعداد الأولية الأقل من 30.

 2 3 5 7 11 13 17 19 23 29

الخوارزمية ومتغيراتها

الشفرة الزائفة

يمكن التعبير عن غربال إراتوستينس في الشفرة الزائفة ، كما يلي: ^{[ 8 ]}^{[ 9 ]}

خوارزمية غربال إراتوستينس هي المدخلات : عدد صحيح n > 1. المخرجات : جميع الأعداد الأولية من 2 إلى n . ليكن A مصفوفة من القيم المنطقية ، مفهرسة بواسطة الأعداد الصحيحة من s إلى n ،في البداية، تم ضبط كل شيء على "صحيح" . لـ i = 2، 3، 4، ...، لا يتجاوز √n  $، إذا$  كانت A [ i ] صحيحة ، لـ j = i² ، ^i²+ ⁱ، i² + 2i ^،i² + 3i ^،... ، لا يتجاوز n ، اجعل A [ j ] : = خطأأعد جميع قيم i التي تحقق الشرط A [ i ] .

تُنتج هذه الخوارزمية جميع الأعداد الأولية التي لا تزيد عن $n$ . وهي تتضمن تحسينًا شائعًا، وهو بدء تعداد مضاعفات كل عدد أولي $i$ من $i² .$ التعقيد الزمني لهذه الخوارزمية هو $O (n log log n)$ ، ^{[ 9 ]} بشرط أن يكون تحديث المصفوفة عملية $O (1)$ ، كما هو الحال عادةً.

منخل مجزأ

كما يشير سورنسون، فإن مشكلة غربال إراتوستينس لا تكمن في عدد العمليات التي يُجريها، بل في متطلبات الذاكرة التي يستهلكها. ^{[ 9 ]} فبالنسبة لقيم $n$ الكبيرة ، قد لا يتسع نطاق الأعداد الأولية في الذاكرة؛ والأسوأ من ذلك، حتى بالنسبة لقيم $n$ المتوسطة ، فإن استخدام ذاكرة التخزين المؤقت يكون دون المستوى الأمثل. إذ يجتاز الخوارزمية المصفوفة $A$ بأكملها ، دون إظهار أي ترابط مرجعي تقريبًا .

يُقدّم الصنفرة المُجزّأة حلاً لهذه المشاكل ، حيث يتم غربلة أجزاء فقط من النطاق في كل مرة. ^{[ 10 ]} وقد عُرفت هذه الصنفرة منذ سبعينيات القرن الماضي، وتعمل على النحو التالي: ^{[ 9 ]}^{[ 11 ]}

قسّم النطاق من 2 إلى $n$ إلى أجزاء ذات حجم $Δ \geq \sqrt n$ .
أوجد الأعداد الأولية في الجزء الأول (أي الأدنى)، باستخدام المنخل العادي.
لكل من الأجزاء التالية، بترتيب تصاعدي، حيث m هي القيمة العليا للجزء، أوجد الأعداد الأولية فيه كما يلي:
1. قم بإنشاء مصفوفة منطقية بحجم $Δ$ .
2. قم بتحديد المواضع في المصفوفة التي تتوافق مع مضاعفات كل عدد أولي $p \leq \sqrt m$ تم العثور عليه حتى الآن على أنها غير أولية، وذلك عن طريق تعداد مضاعفاته بخطوات $p$ بدءًا من أصغر مضاعف لـ $p$ بين $m - Δ$ و $m$ .
3. تمثل المواضع المتبقية غير المميزة في المصفوفة الأعداد الأولية في القطعة. ليس من الضروري تمييز أي مضاعفات لهذه الأعداد الأولية، لأن جميع هذه الأعداد $الأولية$ أكبر من $\sqrtm$ ، حيث أنه بالنسبة لـ $k \geq 1$ ، يكون لدينا $(k\Delta +1)^{2}>(k+1)\Delta$ .

إذا تم اختيار $Δ$ ليكون $\sqrt n$ ، فإن التعقيد المكاني للخوارزمية هو $O (\sqrt n)$ ، بينما يكون التعقيد الزمني هو نفسه التعقيد الزمني للمنخل العادي. ^{[ 9 ]}

بالنسبة للنطاقات ذات الحد الأعلى $n$ الكبير جدًا بحيث لا يمكن استيعاب الأعداد الأولية التي تقل عن $\sqrtn ،$ كما هو مطلوب بواسطة غربال إراتوستينس المجزأ للصفحات، في الذاكرة، يمكن استخدام غربال أبطأ ولكنه أكثر كفاءة في استخدام المساحة مثل غربال الأعداد الأولية شبه المربعة، الذي طوره جوناثان ب. سورنسون، بدلاً من ذلك. ^{[ 12 ]}

المنخل التدريجي

تُنتج الصيغة التزايدية للغربال ^{[ 2 ]} أعدادًا أولية بلا حدود (أي بدون حد أعلى) عن طريق دمج عملية توليد الأعداد الأولية مع عملية توليد مضاعفاتها (بحيث يمكن إيجاد الأعداد الأولية في الفجوات بين المضاعفات)، حيث تُولّد مضاعفات كل عدد أولي $p$ مباشرةً عن طريق العد تصاعديًا من مربع العدد الأولي بزيادات قدرها $p$ (أو $2p للأعداد الأولية الفردية)$ . يجب بدء عملية التوليد فقط عند الوصول إلى مربع العدد الأولي، لتجنب أي تأثيرات سلبية على الكفاءة. ويمكن التعبير عنها رمزيًا في إطار نموذج تدفق البيانات كما يلي:

primes = [ 2 , 3 , ...] \ [[ p ², p ²+ p , ...] for p in primes ],

باستخدام تدوين فهم القوائم مع \الإشارة إلى طرح المجموعات من المتتابعات الحسابية للأعداد.

يمكن أيضًا إنتاج الأعداد الأولية عن طريق غربلة الأعداد المركبة بشكل متكرر من خلال اختبار قابلية القسمة على الأعداد الأولية المتسلسلة، عدد أولي واحد في كل مرة. وهي ليست غربال إراتوستينس، ولكن غالبًا ما يتم الخلط بينهما، على الرغم من أن غربال إراتوستينس يُولّد الأعداد المركبة مباشرةً بدلاً من اختبارها. تتميز عملية القسمة التجريبية بتعقيد نظري أكبر من غربال إراتوستينس في توليد نطاقات الأعداد الأولية. ^{[ 2 ]}

عند اختبار كل عدد أولي، تستخدم خوارزمية القسمة التجريبية المثلى جميع الأعداد الأولية التي لا تتجاوز جذرها التربيعي، بينما ينتج غربال إراتوستينس كل عدد مركب من عوامله الأولية فقط، ويحصل على الأعداد الأولية "تلقائيًا" بين الأعداد المركبة. غالبًا ما يُقدَّم رمز الغربال الوظيفي الشهير لديفيد تيرنر ^{[ 13 ]،} الذي طُوِّر عام 1975 ، كمثال على غربال إراتوستينس ^{[ 7 ]،} ولكنه في الواقع غربال قسمة تجريبية دون المستوى الأمثل. ^{[ 2 ]}

التعقيد الخوارزمي

يُعد غربال إراتوستينس طريقة شائعة لتقييم أداء الحاسوب. ^{[ 14 ]} يبلغ التعقيد الزمني لحساب جميع الأعداد الأولية الأقل من $n$ في نموذج آلة الوصول العشوائي $O (n log log n)$ عملية، وهو نتيجة مباشرة لحقيقة أن متسلسلة التوافقيات الأولية تقترب تقاربًا من $log log n$ . ومع ذلك، فإن تعقيدها الزمني أُسّي بالنسبة لطول المُدخلات، مما يجعلها خوارزمية شبه متعددة الحدود . تتطلب الخوارزمية الأساسية $O (n)$ من الذاكرة.

يبلغ تعقيد البت للخوارزمية $O (n (log n) (log log n))$ عملية بت مع متطلبات ذاكرة قدرها $O (n)$ . ^{[ 15 ]}

تتمتع النسخة المجزأة للصفحات المنفذة بشكل طبيعي بنفس التعقيد التشغيلي $O (n log log n) مثل النسخة غير المجزأة$ $،$ ولكنها تقلل متطلبات المساحة إلى الحد الأدنى لحجم صفحة المقطع بالإضافة إلى الذاكرة المطلوبة لتخزين الأعداد الأولية الأساسية الأقل من الجذر التربيعي للنطاق المستخدم لاستخراج المركبات من مقاطع الصفحات المتتالية بحجم $O (\sqrt n / log n) .$

^{تستخدم نسخة مجزأة خاصة (نادراً ما تُنفذ، إن لم} $يكن$ أبداً) من غربال إراتوستينس، مع تحسينات أساسية، $O (n)$ عملية و $O (\sqrtn log log n / log n)$ بت من الذاكرة. ^[ $16$ ^]^{[ 17 ]}^{[ 18 ]}

يتجاهل استخدام ترميز Big O العوامل الثابتة والإزاحات التي قد تكون ذات أهمية بالغة في النطاقات العملية: يتميز منخل إراتوستينس المُعدَّل، والمعروف باسم منخل بريتشارد ذي العجلة ^{[ 16 ]}^{[ 17 ]}^{[ 18 ]} ، بأداء $O (n) ، لكن تنفيذه الأساسي يتطلب إما خوارزمية "مصفوفة كبيرة واحدة" تحد من نطاق استخدامه إلى مقدار الذاكرة المتاحة$ $،$ أو يتطلب تجزئة الصفحات لتقليل استهلاك الذاكرة. عند تنفيذه بتجزئة الصفحات لتوفير الذاكرة، لا تزال الخوارزمية الأساسية تتطلب حوالي $O (n / log n)$ $بت$ من الذاكرة (أكثر بكثير من متطلبات منخل إراتوستينس الأساسي المُجزَّأ بالصفحات والذي يستخدم $O ($ $\sqrtn$ $/$ $log$ $n$ $) بت$ $من$ $الذاكرة ) . قلل عمل بريتشارد$ $من$ متطلبات الذاكرة على حساب عامل ثابت كبير. على الرغم من أن المنخل العجلي الناتج يتمتع بأداء $O (n)$ ومتطلبات ذاكرة مقبولة، إلا أنه ليس أسرع من منخل إراتوستينس الأساسي ذي العامل العجلي المعقول لنطاقات الغربلة العملية.

منخل أويلر

يتضمن برهان أويلر لصيغة حاصل ضرب زيتا نسخة من غربال إراتوستينس، حيث يُحذف كل عدد مركب مرة واحدة فقط. وقد أعاد غريس وميسرا ( 1978) اكتشاف هذا الغربال نفسه، ولاحظا أنه يستغرق وقتًا خطيًا . ^[¹⁹^] يبدأ هذا الغربال أيضًا بقائمة أعداد مرتبة من 2 إلى $n$ . في كل خطوة، يُحدد العنصر الأول على أنه العدد الأولي التالي، ويُضرب في كل عنصر من عناصر القائمة (بدءًا من نفسه)، وتُعلّم النتائج في القائمة لحذفها لاحقًا. ثم يُزال العنصر الأول والعناصر المُعلّمة من التسلسل العامل، وتُكرر العملية.

 [2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 ...  [3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 ...  [4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ...  [5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ...  [...]

يُعرض هنا المثال بدءًا من الأعداد الفردية، بعد الخطوة الأولى من الخوارزمية. وبالتالي، في الخطوة $k$ ، تُزال جميع مضاعفات العدد الأولي $k$ المتبقية من القائمة، التي ستحتوي بعد ذلك على أعداد أولية نسبياً مع الأعداد الأولية $k$ الأولى فقط (انظر تحليل العجلة )، بحيث تبدأ القائمة بالعدد الأولي التالي، وجميع الأعداد فيها التي تقل عن مربع أول عنصر فيها ستكون أعداداً أولية أيضاً.

وبالتالي، عند توليد متتالية محدودة من الأعداد الأولية، عندما يتجاوز العدد الأولي التالي المحدد الجذر التربيعي للحد الأعلى، تكون جميع الأعداد المتبقية في القائمة أعدادًا أولية. ^{[ 9 ]} في المثال المذكور أعلاه، يتحقق ذلك بتحديد 11 كعدد أولي تالٍ، مما ينتج عنه قائمة بجميع الأعداد الأولية الأقل من أو تساوي 80.

لاحظ أن الأرقام التي سيتم تجاهلها في خطوة ما لا تزال تُستخدم عند تحديد المضاعفات في تلك الخطوة، على سبيل المثال، بالنسبة لمضاعفات العدد 3، يكون الناتج 3 × 3 = 9 ، و3 × 5 = 15 ، و 3 × 7 = 21 ، و 3 × 9 = 27 ، ...، و 3 × 15 = 45 ، ...، لذا يجب توخي الحذر عند التعامل مع هذا الأمر. ^{[ 9 ]}

انظر أيضاً

مراجع

1 2 3 هورسلي، القس صموئيل، FRS، " Κόσκινον Ερατοσθένους أو غربال إراتوستينس. كونه حسابًا لطريقته في العثور على جميع الأعداد الأولية، " المعاملات الفلسفية (1683-1775)، المجلد. 62. (1772)، الصفحات من 327 إلى 347 .
1 2 3 4 أونيل، ميليسا إي، "المنخل الحقيقي لإراتوستينس" ، مجلة البرمجة الوظيفية ، نُشرت على الإنترنت بواسطة مطبعة جامعة كامبريدج في 9 أكتوبر 2008 doi : 10.1017/S0956796808007004 ، الصفحات 10، 11 (تحتوي على منخلين تزايديين في لغة هاسكل: أحدهما قائم على قائمة الانتظار ذات الأولوية من قبل أونيل والآخر قائم على القائمة من قبل ريتشارد بيرد).
^ هوش، ريتشارد ، أد. (1866)، نيكوماشي جيراسيني فيثاغوري مقدمة في علم الحساب الثاني، الفصل الثالث عشر، 3 ، لايبزيغ: بي جي تيوبنر، ص. 30
1 2 نيكوماخوس الجراسي (1926)، مقدمة في الحساب؛ ترجمها إلى الإنجليزية مارتن لوثر دوج؛ مع دراسات في الحساب اليوناني لفرانك إيجلستون روبنز ولويس تشارلز كاربينسكي، الفصل الثالث عشر، 3 ، نيويورك: شركة ماكميلان، ص 204
↑ JC Morehead, "امتداد غربال إراتوستينس إلى المتتابعات الحسابية وتطبيقاتها"، حوليات الرياضيات، السلسلة الثانية 10 :2 (1909)، ص 88-104 .
↑ كلوكسين، ويليام ف.، وكريستوفر س. ميليش، البرمجة بلغة برولوج ، 1984، ص 170. ISBN 3-540-11046-1.
1 2 رونسيمان، كولين (1997). "اللؤلؤة الوظيفية: مناخل العجلة الكسولة واللوالب الأولية" (ملف PDF) . مجلة البرمجة الوظيفية . 7 (2): 219-225 . doi : 10.1017/S0956796897002670 . S2CID 2422563 .
↑ سيدجويك، روبرت (1992). الخوارزميات في لغة C++ . أديسون-ويسلي. ISBN 978-0-201-51059-1.، ص 16.
1 2 3 4 5 6 7 جوناثان سورنسون، مقدمة في غربال الأعداد الأولية ، تقرير فني لعلوم الحاسوب رقم 909، قسم علوم الحاسوب، جامعة ويسكونسن-ماديسون، 2 يناير 1990 (يتم عرض استخدام التحسين بدءًا من المربعات، وبالتالي استخدام الأعداد التي يكون مربعها أقل من الحد الأعلى فقط).
↑ كراندال وبوميرانس، الأعداد الأولية: منظور حسابي ، الطبعة الثانية، سبرينغر: 2005، ص 121-24.
↑ بايز، كارتر؛ هدسون، ريتشارد هـ. (1977). "المنخل المجزأ لإراتوستينس والأعداد الأولية في المتتابعات الحسابية حتى 10^ ¹² ". BIT . 17 (2): 121–127 . doi : 10.1007/BF01932283 . S2CID 122592488 .
↑ ج. سورنسون، "منخل الأعداد الأولية شبه المربعة" ، وقائع الندوة الدولية السابعة حول نظرية الأعداد الخوارزمية . (ANTS-VII، 2006).
↑ تيرنر، ديفيد أ. دليل لغة SASL. تقرير فني CS/75/1. قسم علوم الحاسوب، جامعة سانت أندروز 1975. (). ولكن انظر أيضًا بيتر هندرسون، موريس، جيمس الابن، مُقيِّم كسول، 1976 ، حيث نجد ما يلي ، المنسوب إلى ب. كوارندون:؛ الأولوية غير واضحة.primes=sieve[2..];sieve(p:nos)=p:sieve(remove(multsofp)nos);removem=filter(not.m);multsofpn=remnp==0primeswrt[x;l]=ifcar[l]modx=0thenprimeswrt[x;cdr[l]]elsecons[car[l];primeswrt[x;cdr[l]]];primes[l]=cons[car[l];primes[primeswrt[car[l];cdr[l]]]];primes[integers[2]]
↑ بينغ، تي إيه ( خريف 1985). "مليون عدد أولي عبر الغربال" . بايت . ص 243-244 . تم الاسترجاع في 19 مارس 2016 .
↑ بريتشارد، بول، "المناخل الخطية للأعداد الأولية: شجرة عائلة"، Sci. Comput. Programming 9 :1 (1987)، ص 17-35.
1 2 بول بريتشارد، "منخل جمعي شبه خطي لإيجاد الأعداد الأولية"، اتصالات ACM 24 (1981)، 18-23. MR 0600730
1 2 بول بريتشارد، شرح المنخل ذي العجلة، أكتا إنفورماتيكا 17 (1982)، 477-485. MR 0685983
1 2 بول بريتشارد، "مناخل الأعداد الأولية السريعة والمضغوطة" (من بين آخرين)، مجلة الخوارزميات 4 (1983)، 332-344. MR 0729229
↑ غريس، ديفيد ؛ ميسرا، جاياديف (ديسمبر 1978)، "خوارزمية غربلة خطية لإيجاد الأعداد الأولية" (ملف PDF) ، مجلة اتصالات رابطة مكائن الحوسبة ، 21 (12): 999-1003 ، doi : 10.1145/359657.359660 ، hdl : 1813/6407 ، S2CID 11990373 .

روابط خارجية

primesieve – غربال إراتوستينس المجزأ، سريع للغاية ومُحسَّن بشكل كبير، مكتوب بلغة C/C++
إراتوستينس، غربال في موسوعة الرياضيات
صفحة جافا سكريبت تفاعلية
غربال إراتوستينس لجورج بيك، مشروع مظاهرات ولفرام .
غربال إراتوستينس في هاسكل
شرح وتوضيح خوارزمية غربال إراتوستينس. تطبيقات بلغة جافا وسي++.
غربال إراتوستينس المجزأ عالي التوازي والمُحسَّن بسرعة باستخدام CUDA في C
صفحة ويكي C2 بعنوان "منخل إراتوستين في العديد من لغات البرمجة"
فن غربلة الأعداد الأولية: غربال إراتوستينس بلغة C من عام 1998 مع شرح للميزات الرائعة والحيل الخوارزمية.

[horsley-1] 1 2 3 هورسلي، القس صموئيل، FRS، " Κόσκινον Ερατοσθένους أو غربال إراتوستينس. كونه حسابًا لطريقته في العثور على جميع الأعداد الأولية، " المعاملات الفلسفية (1683-1775)، المجلد. 62. (1772)، الصفحات من 327 إلى 347 .

[ONeill-2] 1 2 3 4 أونيل، ميليسا إي، "المنخل الحقيقي لإراتوستينس" ، مجلة البرمجة الوظيفية ، نُشرت على الإنترنت بواسطة مطبعة جامعة كامبريدج في 9 أكتوبر 2008 doi : 10.1017/S0956796808007004 ، الصفحات 10، 11 (تحتوي على منخلين تزايديين في لغة هاسكل: أحدهما قائم على قائمة الانتظار ذات الأولوية من قبل أونيل والآخر قائم على القائمة من قبل ريتشارد بيرد).

[nicomachus-3] هوش، ريتشارد ، أد. (1866)، نيكوماشي جيراسيني فيثاغوري مقدمة في علم الحساب الثاني، الفصل الثالث عشر، 3 ، لايبزيغ: بي جي تيوبنر، ص. 30

[nicomachus1926-4] 1 2 نيكوماخوس الجراسي (1926)، مقدمة في الحساب؛ ترجمها إلى الإنجليزية مارتن لوثر دوج؛ مع دراسات في الحساب اليوناني لفرانك إيجلستون روبنز ولويس تشارلز كاربينسكي، الفصل الثالث عشر، 3 ، نيويورك: شركة ماكميلان، ص 204

[5] JC Morehead, "امتداد غربال إراتوستينس إلى المتتابعات الحسابية وتطبيقاتها"، حوليات الرياضيات، السلسلة الثانية 10 :2 (1909)، ص 88-104 .

[6] كلوكسين، ويليام ف.، وكريستوفر س. ميليش، البرمجة بلغة برولوج ، 1984، ص 170. ISBN 3-540-11046-1.

[Runciman-7] 1 2 رونسيمان، كولين (1997). "اللؤلؤة الوظيفية: مناخل العجلة الكسولة واللوالب الأولية" (ملف PDF) . مجلة البرمجة الوظيفية . 7 (2): 219-225 . doi : 10.1017/S0956796897002670 . S2CID 2422563 .

[sedgewick-8] سيدجويك، روبرت (1992). الخوارزميات في لغة C++ . أديسون-ويسلي. ISBN 978-0-201-51059-1.، ص 16.

[intro-9] 1 2 3 4 5 6 7 جوناثان سورنسون، مقدمة في غربال الأعداد الأولية ، تقرير فني لعلوم الحاسوب رقم 909، قسم علوم الحاسوب، جامعة ويسكونسن-ماديسون، 2 يناير 1990 (يتم عرض استخدام التحسين بدءًا من المربعات، وبالتالي استخدام الأعداد التي يكون مربعها أقل من الحد الأعلى فقط).

[10] كراندال وبوميرانس، الأعداد الأولية: منظور حسابي ، الطبعة الثانية، سبرينغر: 2005، ص 121-24.

[11] بايز، كارتر؛ هدسون، ريتشارد هـ. (1977). "المنخل المجزأ لإراتوستينس والأعداد الأولية في المتتابعات الحسابية حتى 10^ ¹² ". BIT . 17 (2): 121–127 . doi : 10.1007/BF01932283 . S2CID 122592488 .

[12] ج. سورنسون، "منخل الأعداد الأولية شبه المربعة" ، وقائع الندوة الدولية السابعة حول نظرية الأعداد الخوارزمية . (ANTS-VII، 2006).

[13] تيرنر، ديفيد أ. دليل لغة SASL. تقرير فني CS/75/1. قسم علوم الحاسوب، جامعة سانت أندروز 1975. (). ولكن انظر أيضًا بيتر هندرسون، موريس، جيمس الابن، مُقيِّم كسول، 1976 ، حيث نجد ما يلي ، المنسوب إلى ب. كوارندون:؛ الأولوية غير واضحة.primes=sieve[2..];sieve(p:nos)=p:sieve(remove(multsofp)nos);removem=filter(not.m);multsofpn=remnp==0primeswrt[x;l]=ifcar[l]modx=0thenprimeswrt[x;cdr[l]]elsecons[car[l];primeswrt[x;cdr[l]]];primes[l]=cons[car[l];primes[primeswrt[car[l];cdr[l]]]];primes[integers[2]]

[peng1985fall-14] بينغ، تي إيه ( خريف 1985). "مليون عدد أولي عبر الغربال" . بايت . ص 243-244 . تم الاسترجاع في 19 مارس 2016 .

[15] بريتشارد، بول، "المناخل الخطية للأعداد الأولية: شجرة عائلة"، Sci. Comput. Programming 9 :1 (1987)، ص 17-35.

[Pritchard1-16] 1 2 بول بريتشارد، "منخل جمعي شبه خطي لإيجاد الأعداد الأولية"، اتصالات ACM 24 (1981)، 18-23. MR 0600730

[Pritchard2-17] 1 2 بول بريتشارد، شرح المنخل ذي العجلة، أكتا إنفورماتيكا 17 (1982)، 477-485. MR 0685983

[Pritchard3-18] 1 2 بول بريتشارد، "مناخل الأعداد الأولية السريعة والمضغوطة" (من بين آخرين)، مجلة الخوارزميات 4 (1983)، 332-344. MR 0729229

[19] غريس، ديفيد ؛ ميسرا، جاياديف (ديسمبر 1978)، "خوارزمية غربلة خطية لإيجاد الأعداد الأولية" (ملف PDF) ، مجلة اتصالات رابطة مكائن الحوسبة ، 21 (12): 999-1003 ، doi : 10.1145/359657.359660 ، hdl : 1813/6407 ، S2CID 11990373 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]،

[ 14 ]

[ 15 ]

تستخدم نسخة مجزأة خاصة (نادراً ما تُنفذ، إن لم

[ 17 ]

[ 18 ]

[

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗