ابدأ في العلم. غربال إراتوستينس - خوارزمية لتحديد الأعداد الأولية

05.05.2019

) مستبعدة.

يوتيوب الموسوعي

1 / 5

✪ غربال إراتوستينس على سي

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

✪ المحاضرة 44: غربال إراتوستينس

✪ الأعداد الأولية. الرياضيات

ترجمات

قصة

حصلت هذه الطريقة على اسم "الغربال" لأن إراتوستينس، وفقًا للأسطورة، كتب الأرقام على لوح مغطى بالشمع وأحدث ثقوبًا في الأماكن التي كتبت فيها الأرقام المركبة. ولذلك، كان اللوح بمثابة نوع من الغربال، الذي يتم من خلاله "غربلة" جميع الأرقام المركبة، وتبقى الأعداد الأولية فقط. إراتوستينس أعطى جدول الأعداد الأولية حتى 1000.

خوارزمية

دليل على التعقيد

عند التحديد n ∈ N (\displaystyle n\in \mathbb (N))لكل رئيس الوزراء ص ∈ P: p ≥ n (\displaystyle p\in \mathbb (P) \colon p\leq n)سيتم تنفيذ الحلقة الداخلية، والتي سوف تكتمل ن ص (\displaystyle (\frac (n)(p)))أجراءات. ولذلك، علينا تقدير الكمية التالية:

∑ p ∈ P: p ≥ n n p = n ⋅ ∑ p ∈ P: p ≥ n 1 p (\displaystyle \sum \limits _(p\in \mathbb (P) \colon p\leq n)(\frac (n) )(p))=n\cdot \sum\limits _(p\in \mathbb (P) \colon p\leq n)(\frac (1)(p)))

كود مزيف

التنفيذ الأمثل (بدءًا بالمربعات) في الكود الكاذب:

مدخل: عدد طبيعي نيترك أ- مجموعة منطقية مفهرسة بالأرقام من 2 إلى ن، مليئة في البداية بالقيم حقيقي. ل أنا := 2, 3, 4, ..., الوداع أنا 2 ≤ ن: لو أ[أنا] = حقيقي: ل ي := أنا 2 , أنا 2 + أنا, أنا 2 + 2أنا, ..., الوداع ي ≤ ن: أ[ي] := خطأ شنيع مخرج: أعداد أنا، لأي منهم أ[أنا] = حقيقي.

مثال على ن = 30

لنكتب الأعداد الطبيعية من 2 إلى 30 على التوالي:

الرقم الأول في القائمة، 2، هو عدد أولي. لنمر عبر سلسلة من الأرقام، مع شطب جميع الأرقام التي هي من مضاعفات الرقم 2 (أي كل ثانية، بدءًا من 2 2 = 4):

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، هو عدد أولي. لنمر عبر سلسلة من الأرقام، مع شطب جميع الأرقام التي هي مضاعفات الرقم 3 (أي كل ثلث، بدءًا من 3 2 = 9):

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، هو عدد أولي. دعنا نمر عبر سلسلة من الأرقام، مع شطب جميع الأرقام التي هي مضاعفات الرقم 5 (أي كل خمس، بدءًا من 5 2 = 25). إلخ.

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

الرقم التالي غير المتقاطع هو 7. ومربعه 49 أكبر من 30، وبذلك يكون العمل قد اكتمل. لقد تم بالفعل شطب جميع الأرقام المركبة:

2 3 5 7 11 13 17 19 23 29

تعديلات الطريقة

خيار تدريجي وغير محدود

في هذا الخيار يتم حساب الأعداد الأولية بشكل تسلسلي، دون قيود عليا، حيث أن الأرقام الموجودة في الفراغات بين الأعداد المركبة، والتي يتم حسابها لكل رقم أولي ص، ابتداء من مربعه، بزيادات ص(أو للأعداد الأولية الفردية 2 ص) . يمكن تمثيلها رمزيا في نموذج تدفق البيانات كما

الأعداد الأولية = [2 ..] \ [[ص*ص, ص*ص+ص..]ل صفي الأعداد الأولية]

العدد الأولي الأول 2 (بين الأعداد الصحيحة الموجبة المتزايدة) معروفة مسبقًا، لذلك لا توجد حلقة مفرغة في هذا التعريف المرجعي الذاتي.

تعداد المقسومات

غالبًا ما يتم الخلط بين غربال إراتوستينس والخوارزميات التي تقوم بتصفية الأرقام المركبة من فترة زمنية معينة عن طريق اختبار كل رقم من الأرقام المرشحة عن طريق القوة الغاشمة للمقسومات.

كود مزيف

مدخل: عدد طبيعي نيترك العلاقات العامة- مصفوفة عددية، فارغة في البداية؛ lp- مجموعة أعداد صحيحة مفهرسة من 2 إلى ن، مليئة بالأصفار ل أنا := 2, 3, 4, ..., قبل ن: لو lp[أنا] = 0 : lp[أنا] := أنا العلاقات العامة += {أنا} ل صمن العلاقات العامةالوداع ص ≤ lp[أنا] و باي ≤ ن: lp[باي] := ص مخرج: جميع الأرقام في المصفوفة العلاقات العامة.

يعد غربال إراتوستينس أقدم طريقة معروفة لكتابة الأعداد الأولية. وخلافا للطرق التي تمت مناقشتها في الفقرات السابقة، فإنه لا يستخدم أي وظيفة خاصة. كان إراتوستينس عالم رياضيات يونانيًا ولد حوالي عام 284 قبل الميلاد. ه. لقد أتقن العديد من فروع المعرفة، لكن معاصريه لم يعتبروه متخصصا بارزا في أي منها. أطلقوا عليه لقب "بيتا" (الحرف الثاني من الأبجدية اليونانية) و"بنتاثلوس". نحن نستخدم عمله منذ 2300 عام، والألقاب التي حصل عليها هي تأكيد إضافي على عظمة الرياضيات اليونانية القديمة.

"إن طريقة الحصول على هذه [الأعداد الأولية] تسمى، وفقًا لإراتوستينس، غربالًا، لأننا نأخذ جميع الأعداد الفردية، ونخلطها معًا بشكل عشوائي، ونتخلص منها، كما هو الحال مع أي نوع من الأدوات أو الغربال، فإننا نفصل أولاً وغير القابلة للتحلل، وثانيًا المركبة بذاتها."

لمزيد من القراءة لقول نيقوماخوس عن الغربال، انظر.

لذلك، حصل الغربال على اسمه لأنه عندما يتم تطبيقه على قائمة الأعداد الطبيعية، يتم غربلة الأعداد المركبة بينما يتم الاحتفاظ بالأعداد الأولية. دعونا نرى كيف يعمل.

أولًا، الغرض من الغربال هو تحديد جميع الأعداد الأولية الموجبة الأقل من بعض الحد الأعلى

والتي نفترض أنها سليمة. لاستخدام طريقة الغربال كما فعل إراتوستينس (باستخدام قلم وورقة فقط)، نتبع ما يلي. أولا نكتب جميع الأعداد الصحيحة الفردية بينهما. السبب وراء عدم لمسنا للأعداد الزوجية هو أنه، باستثناء الرقم 2، لا توجد أعداد أولية بينها.

الآن نبدأ في غربلة القائمة. الرقم الأول فيه هو 3. بدءًا من الرقم التالي في القائمة (هذا هو 5)، نقوم بشطب كل رقم ثالث منه. بعد القيام بذلك حتى النهاية، سنقوم بشطب جميع الأرقام من القائمة التي هي مضاعفات الرقم 3 وأكبر من 3 نفسه.

الآن دعونا نختار أصغر رقم من القائمة أكبر من 3 ولم يتم شطبه بعد. سيكون هذا 5، والرقم التالي بعده سيكون 7. نقوم بشطب كل رقم خامس من قائمتنا، بدءًا من 7. وبالتالي، سيتم شطب جميع الأرقام التي هي مضاعفات الرقم 5. نستمر بهذا الإجراء حتى نصل إلى ملاحظة أنه إذا كنا سنقوم بشطب كل رقم، فيجب علينا دائمًا أن نبدأ العد من الرقم حتى لو تم شطب هذا الرقم في الخطوات السابقة.

على سبيل المثال، تبدو قائمة الأرقام الفردية كما يلي:

بشطب كل رقم ثالث بدءًا من الرقم 5، نحصل على

الآن نقوم بشطب كل رقم خامس، بدءًا من الرقم 7، وهو ما يعطينا

سيتعين علينا الآن شطب كل رقم سابع، بدءًا من الرقم 9. لكن إذا فعلنا ذلك، فلن تكون هناك أرقام جديدة

لن التسرب. بعد ذلك، علينا شطب كل رقم حادي عشر، بدءًا من الرقم 13، لكن هذا لن يكون له أي تأثير مرة أخرى. في الواقع، لن يتم شطب أي من الأرقام المتبقية في القائمة بعد شطب كل رقم خامس في أي مرحلة غربلة. إذن، الأعداد الأولية الفردية الموجبة التي لا تتجاوز 41 هي

في المثال الذي تمت مناقشته، هناك بعض الظروف المهمة التي يجب أخذها في الاعتبار. أولاً، على الرغم من أنه كان ينبغي علينا تكرار عملية الحذف حتى الوصول إلى الرقم المقطوع (41 في مثالنا)، فقد تخلصنا من جميع الأرقام المركبة بحلول الوقت الذي حذفنا فيه مضاعفات الرقم 5، مما جعل جميع عمليات الغربلة الأخرى غير ضرورية . ثانيا، تم شطب بعض الأرقام أكثر من مرة. حدث هذا مع الرقم 15، على سبيل المثال، في المرة الأولى التي تم فيها شطبه عندما حذفنا مضاعفات الرقم 3. لكن الرقم 15 يقبل القسمة أيضًا على 5، لذلك تم شطبه مرة أخرى عندما حذفنا مضاعفات الرقم 5.

دعونا نرى كيف يمكننا زيادة كفاءة المنخل في ضوء هاتين الملاحظتين. لنبدأ بالثاني منهم، أي. دعونا نرى ما إذا كان بإمكاننا تنظيم كل شيء بحيث يتم شطب كل رقم مرة واحدة فقط؟ من المؤسف أن الإجابة على هذا السؤال هي لا: لا توجد طريقة جيدة لتحقيق ذلك. على الرغم من أنه لا يزال من الممكن القيام بشيء ما في هذا الاتجاه.

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

مضاعف الرقم الذي لا يقبل القسمة على عدد أولي يكون أصغر، لذلك يكفي شطب كل رقم، بدءًا من ذلك، ومع ذلك، لا بد من الانتباه إلى حقيقة أنه حتى بعد هذا الابتكار ستكون هناك أرقام ستكون كذلك. يتم شطبها أكثر من مرة.

ومن ناحية أخرى، هل يمكننا إنهاء عملية التصفية قبل أن نصل إلى الخطوة؟ هذه المرة الجواب هو نعم، وهذا يتبع ما فعلناه للتو. لنفترض، على سبيل المثال، أننا شطبنا كل رقم. كما رأينا للتو، فإن الرقم الأول الذي سيتم شطبه هو ولكن إذا لم يكن هذا الرقم موجودًا في القائمة فيمكننا نسيانه. ونتيجة لذلك، نحتاج إلى شطب كل واحد حتى يكون عددًا صحيحًا، وهذا يعادل في المثال الذي تمت مناقشته أعلاه، ولهذا السبب كان تجاهل مضاعفات 3 و5 كافيًا لالتقاط جميع الأرقام المركبة من القائمة.

يجب علينا الآن مناقشة تنفيذ الكمبيوتر للغربال. يتم تمثيل قائمة الأرقام الفردية بمصفوفة أحادية البعد، والتي تسمى أيضًا بالمتجه. تذكر أن كل خلية في المتجه لها رقمان مرتبطان بها. أحدهما هو قيمة الخلية، والآخر يحدد موقعها في المتجه. على سبيل المثال، في ناقلات

قيمة الخلية المميزة بالسهم متساوية ومؤشرها اثنان، لأنها في المركز الثاني في المتجه.

دعنا نعود إلى غربال إراتوستينس. لنفترض أننا نريد العثور على جميع الأعداد الأولية التي لا تزيد عن عدد صحيح فردي، يجب علينا أولاً إنشاء متجه باستخدام الخلايا، واحد لكل عدد صحيح فردي، وستأخذ الخلايا إحدى القيمتين المحتملتين: 1 أو 0. إذا كانت قيمة الخلية هو 0، ثم الرقم الفردي بها

المقدمة، تم شطبها في بعض الخطوات السابقة في عملية الغربلة. لذا فإن القيمة الأولية لكل خلية هي 1 نظرًا لعدم وجود أرقام مشطوبة حتى الآن. "لشطب" رقم ما، تحتاج إلى استبدال الرقم 1 الموجود في الخلية المتجهة بالرقم 0. بالطبع، كان من الممكن "شطب" هذه الخلية في خطوة الغربال السابقة. في هذه الحالة، قيمتها هي 0 بالفعل ولن تتغير خلال الخطوات التالية للخوارزمية.

الآن سنقدم نسخة أكثر أو أقل تفصيلا من الخوارزمية الخاصة بغربال إراتوستينس، والتي تم وصفها أعلاه. أنه يحتوي على كل من التحسينات التي ناقشناها، أي. يتم شطب كل رقم بدءًا من وتنتهي الخوارزمية بمجرد تجاوزه

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

الإدخال: طبيعي غريب

المخرجات: قائمة بجميع الأعداد الأولية الموجبة الفردية الأصغر من أو تساوي

الخطوة 1. نبدأ بإنشاء متجه من الخلايا، لكل منها القيمة 1، ونضعها

الخطوة 2. إذا كتبنا جميع الأرقام التي تساوي قيمة الخلية المتجهة لها 1 وتوقفنا؛ بخلاف ذلك، انتقل إلى الخطوة 3.

الخطوة 3. إذا كانت قيمة الخلية المتجهة ذات الرقم هي 0، قم بزيادة بمقدار 2 والعودة إلى الخطوة 2؛ بخلاف ذلك، انتقل إلى الخطوة 4.

يعد غربال إراتوستينس أحد أقدم الخوارزميات التي تسمح لك بالعثور على أرقام تسمى "الأعداد الأولية". أولئك. الأعداد التي لا تقبل القسمة إلا على الواحد وعلى نفسها دون باقي. على سبيل المثال، الرقم 2. أي من الأعداد الطبيعية (الصحيحة) يمكنك قسمة 2 عليها حتى لا تحصل على باقي؟ فقط بـ 2 و 1. أو الرقم 7. نفس الشيء. وبدون باقي، فإنه ينقسم مرة أخرى إلى نفسه وإلى واحد فقط.

تم اختراع خوارزمية بسيطة إلى حد ما من قبل الرجل الماكر إراتوستينس القيرواني حتى قبل عصرنا. اليونانية حسب الجنسية. عالم رياضيات، عالم فلك، جغرافي. يعد غربال إراتوستينس خوارزمية بحث شائعة إلى حد ما.

هذه الخوارزمية في الواقع لا تتطلب أي وصف خاص. أنها تنطوي على دورتين من المشي من خلال مجموعة من الأرقام. الأول يحدد الرقم الأولي التالي، والثاني، المضمن فيه، يشطب جميع الأعداد المركبة (وفقًا لصيغة معينة) التي تأتي بعد هذا الرقم الأولي. يجب أن نحجز على الفور أن الدورة الثانية لا تشطب جميع الأعداد المركبة مرة واحدة.

يقوم بشطب الأعداد التالية بعد العدد الأولي، والتي تقع على مسافة معينة من هذا العدد الأولي. يتم حساب هذه المسافة باستخدام الصيغة: مربع العنصر الحالي + قيمة هذا العنصر.

على سبيل المثال، إذا كان الرقم 5 أوليًا، فإن الرقم الذي يليه والذي يجب شطبه سيكون يساوي 5*5 = 10، ثم 5*5+5 = 15، ثم 5*5+5+5 = 20...وهكذا. بهذه الطريقة، يتم شطب الأعداد التي هي مضاعفات هذا العدد الأولي الذي تم العثور عليه. العثور على عدد أولي يبدأ بالرقم 2. وعليه، يتم شطب 2*2، 2*2+2، 2*2+2+2...

يوجد رسم توضيحي جيد على موقع ويكيبيديا:

خذ الرقم الأولي الأول 2 (الدائرة الزرقاء) وشطب جميع الأرقام التي هي مضاعفات الرقمين (تقاطعات زرقاء). ثم نأخذ الرقم الأولي 3 (الدائرة الخضراء) ونشطب كل ما هو مضاعف له (الصلبان الخضراء)، وما إلى ذلك.

بعد شطب الأرقام من القائمة، من السهل تحديد الرقم الأولي التالي - سيكون الأول الذي لم يتم شطبه بعد الرقم الحالي.

نظرًا لأن الكود نفسه ليس كبيرًا جدًا، فلن أقوم بتقسيمه إلى كتل، فلا يوجد ما يمكن تحديده هناك. على سبيل المثال، يبدو مثل هذا:

خوارزمية البحث: غربال إراتوستينس

#يشمل استخدام اسم للمحطة؛ int main() ( int n = 100; // عد الأرقام قبل // اطلب المصفوفة int *a = new int; // املأها بأرقام المنخل for (int i = 0; i<= n; i++) a[i] = i; //*********************************************************** //Проводим главный цикл. - Начало работы решета for (int i = 2; i * i <= n; i++) { if (a[i]) //Если текущее число не равно 0 - начинаем от него искать сложные for (int j = i*i; j <= n; j += i) //И обнуляем их ячейки, чтобы больше не проверять их в цикле a[j] = 0; } // Решето окончило отсев - в массиве остались только простые //************************************************************ //Выводим необнуленные - простые for (int i = 2; i < n; i++) { if (a[i]) { cout << a[i] << " "; } } cout << endl << endl; delete a; //И освобождаем массив return 0; }

#يشمل

استخدام اسم للمحطة ؛

انت مين()

كثافة العمليات ن = 100؛ // عد الأرقام قبل هذا

//اطلب مصفوفة

int * a = int جديد [ n + 1 ] ;

// املأها بأرقام المنخل

من أجل (int i = 0؛ i<= n ; i ++ )

أ[i] = أنا;

//***********************************************************

// نفذ الحلقة الرئيسية. - بدء تشغيل الغربال

من أجل (int i = 2؛ i * i<= n ; i ++ )

إذا (أ [أنا])

// إذا كان الرقم الحالي لا يساوي 0، نبدأ في البحث عن أرقام معقدة منه

من أجل (int j = i * i ; j<= n ; j += i )

// وأعد ضبط خلاياهم حتى لا نتحقق منها بعد الآن في الحلقة

أ[ي] = 0;

// انتهى الغربال من الفحص - لم يبق سوى الأعداد الأولية في المصفوفة

//************************************************************

// إخراج تلك غير الصفرية - تلك البسيطة

من أجل (int i = 2؛ i< n ; i ++ )

إذا (أ [أنا])

cout<< a [ i ] << " " ;

cout<< endl << endl ;

حقيقي خطأ شنيع)، واستخدم أرقامًا بسيطة لحساب عدد العناصر التي ستحتوي بعد الغربلة حقيقيلكنني قررت أن الأمر لم يكن واضحًا جدًا.

بعد وضع الأرقام في المصفوفة (1,2,3,4,5,6,7,8,9,10...n) يمكنك البدء في غربلتها. حتى الآن، في المرحلة الأولية، يعتبر البرنامج جميع الأرقام الموجودة في الغربال أولية. التكرار الأول للحلقة يأخذ الرقم الأول (أو بالأحرى الثاني) – 2. من هذا الرقم، تقوم الحلقة الثانية بإعادة تعيين عناصر المصفوفة التي تقع تحت شرط المرشح الرقم*الرقم+الرقم.

بهذه الطريقة، يتم غربلة الأعداد التي تكون مضاعفات العدد اثنين بعد اثنين. بعد ذلك، تواصل الحلقة الأولى مرورها، والتحقق من الحالة إذا (أ [أنا]) , أولئك. هل يوجد رقم في الخلية يختلف عن الصفر (فبعد كل شيء، نحن نقوم بتصفية الأعداد المركبة). بمجرد العثور على مثل هذا الرقم، ستعمل الحلقة الثانية منه مرة أخرى، مع إعادة تعيين الأرقام التي تعد مضاعفاته إلى الصفر بعد العثور عليه. , يقف خلفه.

وهكذا تقوم الدورات بغربلة الأرقام حتى تصل إلى حد الغربلة الذي حددناه - إلى أي رقم يتم التقاط الأعداد الأولية.

أين يتم استخدام الأعداد الأولية؟ حسنًا... على سبيل المثال في التشفير. أيضًا في بعض مولدات الأرقام العشوائية. وبالطبع في الجامعات :) في الواقع، لا يحتقر المعلمون أيضًا الغربال ويقومون بانتظام بتدليل الطلاب بمهارة بمهام "العثور على رقم أولي". بمساعدة مثل هذا المنخل، هذه المشكلة قابلة للحل تماما.

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

4.8 (96.67%) 6 أصوات

الرياضيات علم ظهر منذ عدة آلاف من السنين وكان يستخدم بنشاط بالفعل في اليونان القديمة. في الوقت نفسه، قام العديد من العلماء النظريين الذين عاشوا في ذلك الوقت باكتشافات أصبحت عظيمة ورائعة، لكنهم تلقوا اعترافًا حقيقيًا بعد عدة قرون، عندما مكنت التكنولوجيا من فهم الإمكانات الكاملة للبحث في علم الحساب القديم. ومن الجدير بالذكر أن جميع الحسابات في العصور البعيدة تم إجراؤها "في العقل" أو احتوت على سجلات واسعة النطاق للحسابات. كان إراتوستينس أحد أشهر المتخصصين اليونانيين، ويُطلق عليه بشكل غير رسمي الجد الأكبر للبرمجة. مع ظهور علوم الكمبيوتر، كانت حساباته ونظرياته وبديهياته هي التي غالبًا ما يتم تحويلها إلى "لغات" حاسوبية. كان لدى عالم الرياضيات العديد من الاكتشافات المثيرة للاهتمام في ترسانته، ولكن الأكثر شيوعا كان غربال إراتوستينس، مما يساعد على العثور بسرعة على رقم أولي من تسلسل معين.

سيرة العالم

على الرغم من أن جميع أنشطة المتخصص جرت على أراضي اليونان القديمة، إلا أن عبقري المستقبل ولد في أفريقيا في القرن الثالث قبل الميلاد. درس العالم في أكبر مدن اليونان، حيث بقي ليعيش بشكل دائم. كان أساتذته من الشعراء والفلاسفة والنحويين المشهورين في ذلك الوقت.

بفضل تطوره المتنوع واحترامه بين الأشخاص ذوي التفكير المماثل، تمت دعوة المنظر العبقري إلى منصب خدم فيه حتى وفاته، حيث ابتكر أعمالًا وأبحاثًا في مختلف المجالات التي كانت لا تصدق في تلك الحقبة، بما في ذلك غربال إراتوستينس. تحدث عنه العالم المعاصر، أرخميدس الأسطوري، بعبارات تملقه فقط، بل وخصص عملاً منفصلاً لعمله.

الإنجازات

السمة الرئيسية للعالم القديم تعتبر بحق تنوع المجالات التي تمت دراستها. وفي الوقت نفسه، حقق نتائج باهرة في جميع المجالات تقريبًا. الفلسفة والشعر والرياضيات وعلم الفلك والموسيقى وفقه اللغة والجغرافيا - لمثل هذه العالمية الفريدة في البحث عن المعرفة، حصل المنظر على لقب الخماسي، من خلال الارتباط بالرياضات الشاملة. وبطبيعة الحال، لم يصبح عظيما في أحد المجالات التي درسها، لكنه تمكن في كل منها من تحقيق نتائج جيدة.

ويتجلى ذلك من خلال الأجزاء الباقية من أعماله وأبحاثه. على الرغم من كونه إلى حد ما في ظل معاصريه، فقد قدم العالم مساهمة كبيرة في تاريخ الرياضيات، وأصبح غربال إراتوستينس، إلى جانب عدد من الحسابات الشهيرة الأخرى، بحق واحدًا مع الاكتشافات الهندسية والحسابية الشهيرة.

تاريخ الاسم وتفاصيل الموقع

في العصور القديمة، تم إجراء جميع السجلات، بما في ذلك الحسابات الرياضية، على أقراص شمعية خاصة. لذلك، عند إجراء حسابات ذات طبيعة جبرية وحسابية، خاصة عند حذف الأرقام المتسلسلة، قام العلماء "بثقبها" على أدوات الكتابة.

بعد كل العمل، كان اللوح يشبه الكائن الذي تم إجراء البحث عليه وتم تسميته - غربال إراتوستينس . كان الدافع وراء هذا الاكتشاف هو أفكار العبقرية حول إيجاد الأعداد الأولية في السلسلة الطبيعية. واستمر العمل عدة أشهر حتى تم التوصل إلى النتيجة النهائية. وفي القرن الثالث قبل الميلاد أصبح اختراقا حقيقيا.

ما هي الخوارزمية؟

طريقة سريعة للعثور على كل شيء في السلسلة الطبيعية أثارت اهتمام العلماء منذ زمن سحيق. بعد كل شيء، ليس لديهم تسلسل صارم ويتم ترتيبهم بترتيب عشوائي مشروط. في الوقت الحالي، اكتشف الخبراء الكثير من الأشياء وتعلموا كيفية إجراء الحسابات اللازمة بسرعة كافية. ساعدتهم خوارزمية بسيطة في ذلك - غربال إراتوستينس. لقد اكتشفها العبقري القديم على عدة مراحل:

لفترة طويلة، اعتبر هذا الخيار هو الوحيد الفعال، ومع ظهور علوم الكمبيوتر، تمكن المتخصصون من حساب تسلسلات أكثر تعقيدا. علاوة على ذلك، حتى مع التقنيات الجديدة، فإن غربال إراتوستينس هو النظرية الرياضية الأكثر أهمية.

لغات البرمجة في مجال الحسابات الحسابية

أتاحت التكنولوجيا والكمبيوتر وعلوم الكمبيوتر لعلماء الرياضيات الذين يدرسون النظريات الجبرية الدخول إلى مرحلة جديدة في تطور العلوم. أول شيء فعلوه هو الاستفادة من هذه الفرصة الفريدة لدمج الأبحاث الحسابية والهندسية المعروفة في البرمجة. وأصبحت لغة باسكال واحدة من أشهر لغات الحوسبة الإلكترونية في ذلك الوقت، بما في ذلك حساب خوارزمية الغربال إراتوستينس. وبمساعدتها، كان من الممكن في بضع ثوانٍ العثور على الأعداد الأولية في سلسلة من الأعداد الطبيعية التي لم يكن من الممكن الوصول إليها لفترة طويلة أو تم حسابها من خلال تسجيلات مكثفة، واستغرقت الكثير من الوقت. ونتيجة لذلك، تلقى الأساس العملي للإمكانات الجديدة نسخة محسنة من الاكتشاف القديم وإمكانيات حسابية غير محدودة عمليا.

استخدامها في الأولمبياد الحديث في علوم الكمبيوتر

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

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

تبديل القائمة

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

دعونا نتذكر ذلك رقم اولي، هو عدد يمكن قسمته بدون باقي على نفسه فقط، وبالطبع على واحد. من المحتمل أنك تتذكر في المدرسة بعض الأعداد الأولية - وهي 5، 7، 11، 13، 17، وما إلى ذلك. دعونا الآن نلقي نظرة على مبدأ تشغيل خوارزمية البحث عن الأعداد الأولية. طريقة البحث هذه بسيطة للغاية، لذلك إذا كنت ترغب في ذلك، فسوف يصبح كل شيء واضحًا لك بسرعة كبيرة.

غربال إراتوستينس - خوارزمية العمل. لغة برمجة سي++

1. على سبيل المثال، سوف نبحث عن الأعداد الأولية في النطاق من 0 إلى 1000. للقيام بذلك، نحتاج إلى إنشاء مصفوفة من العناصر المنطقية بأبعاد 1000. ستفهم سبب كونها منطقية لاحقًا. قم بتعريف مصفوفة

حجم ثابت = 1000؛ صفيف منطقي؛

2. الآن نحن بحاجة إلى تعيين قيم أولية لعناصر المصفوفة، لأن في الوقت الحالي تحتوي على "قمامة" مختلفة للنظام. لنقم بذلك: قم بتعيين القيم "صحيح" لجميع عناصر المصفوفة - صحيح أو واحد. عندما تعمل خوارزمية البحث عن الأعداد الأولية، فإن جميع عناصر المصفوفة (لقد قمنا بضبطها مبدئيًا على القيمة true) مع مؤشرات "بسيطة" (لاحظ أننا هنا نتحدث على وجه التحديد عن المؤشرات، نظرًا لأن الأعداد الأولية المرغوبة لدينا ستكون المعبر عنها في فهارس قيم عناصر المصفوفة) ستظل مساوية لـ "صحيح"، وسيتم تعيين جميع العناصر الأخرى على "خطأ" - خطأ، أو صفر. أولئك. الآن أنت تفهم سبب احتواء صفيفنا على قيم منطقية، وإذا كان هناك شيء غير واضح، فبعد تحليل الكود، سوف يقع كل شيء في مكانه. نحن نملأ المصفوفة بدءًا من الخلية الثانية، لأن 0 و 1 لا يعتبران أوليين، مما يعني أنه يمكن استبعادهما على الفور

من أجل (int k = 2؛ k< size; k++) array[k] = true;

3. والآن الشيء الأكثر أهمية: دعونا نلقي نظرة على خوارزمية العثور على الأعداد الأولية نفسها، أي. منخل إراتوستينس نفسه

من أجل عرض المصفوفة ومؤشراتها، نحتاج إلى حلقة - نقوم بعمل حلقة (لا ننظر إلى المؤشرات 0 و1). في هذه الحلقة سوف ننظر من خلال القيم من 2 إلى جذر الحجم. لماذا هذا؟ لأنه بعد الوصول إلى جذر الحجم، سيتم بالفعل حذف جميع الأرقام التي ليست أعدادًا أولية. من خلال القيام بذلك، نقوم بتقليل عدد التكرارات، وبالتالي الحمل على معالج الكمبيوتر، وهو أمر جيد.

من أجل (int i = 2؛ i< sqrt(size); i++) { }

للغربلة، يقع العنصر الأول من المصفوفة ذات القيمة الحقيقية على منخل إراتوستينس. في بداية البرنامج، سيكون هذا العنصر هو العنصر ذو الفهرس 2. بعد ذلك، يتم تنفيذ شرط if وينتهي بنا الأمر في حلقة for الداخلية، والتي تعمل على عرض بقية المصفوفة (من 3 إلى 1000 مؤشر ). سيتم التحقق من قيمة كل مؤشر، ويتم التعبير عن أرقامنا بالأرقام القياسية، للتأكد من وجود باقي عند القسمة على 2. إذا كان الرقم قابلاً للقسمة بدون باقي، فهذا يعني أنه لم يعد من الممكن أن يكون أوليًا وبالتالي، وفقًا لذلك ، قمنا بتعيين هذه الخلية على خطأ. دعونا نلقي نظرة على الكود

من أجل (int i = 2؛ i< sqrt(size); i++) { if(array[i] == true) { for(int j = i * 2; j < size; j++) { if(j % i == 0) array[j] = false; } } }

لتوضيح ما سيحدث بعد التكرار الأول بشكل أكثر وضوحًا، حيث i = 2، إليك صورة لمصفوفة مكونة من 20 قيمة، بالقياس، ستفهم ما يحدث مع مصفوفتنا المكونة من 1000 عنصر.

كما ترون، تم غربلة جميع عناصر المصفوفة التي تحتوي على قيم فهرس من مضاعفات الرقم اثنين ووضع علامة عليها على أنها خاطئة. هذا هو ما يقرب من نصف قيم مجموعتنا بأكملها.

ننتقل إلى التكرار التالي، حيث i = 3. تم استيفاء شرط if، لأن 3 لم يتم "غربلته" في التكرار السابق، وانتهى بنا الأمر مرة أخرى في الحلقة الداخلية، التي تعالج الجزء المتبقي من المصفوفة (المؤشرات من 4 إلى 1000).

ويوضح الشكل أدناه الصورة الناتجة.

كما ترون، تم استبعاد جميع الأرقام التي كانت من مضاعفات العدد ثلاثة ولم يتم استبعادها مسبقًا بواسطة "اثنين".

ننتقل إلى التكرار التالي، حيث i = 4. هنا لم يتم استيفاء شرط if، لذلك لن يتم "غربلة" أي شيء. بعد ذلك، التكرار التالي مع i = 5، هنا سيتم وضع علامة على قيم المصفوفة ذات المؤشرات التي هي مضاعفات 5، والتي لم يتم تحديدها مسبقًا وفقًا لمعايير أخرى، على أنها خاطئة: 25، 35، 45 وما إلى ذلك سيتم استبعاده. التكرارات "العملية" التالية التي سيتم فيها إجراء "الفحص" هي التكرارات مع i = 7، 11، 13، 17 وما إلى ذلك، حتى جذر الحجم (حيث أنه يوجد بعده رقم غير مرتبط بالبسيط).

4. المرحلة الأخيرة من خوارزمية "منخل إراتوستينس" هي طباعة النتائج. لعرض النتائج سنستخدم الحلقة التالية:

من أجل (int i = 2؛ i< mySize; i++) { if(myArray[i] == true) cout << i << endl; }

5. نتيجة العمل:

خوارزمية للعثور على الأعداد الأولية - غربال إراتوستينس في لغة C++. الطريقة الأولى

// خوارزمية للعثور على الأعداد الأولية - غربال إراتوستينس #include // النموذج الأولي للوظيفة void printarray(bool, const int); استخدام اسم للمحطة؛ int main() ( const int size = 1000; صفيف منطقي; for(int k = 2; k< size; k++) array[k] = true; for(int i = 2; i < sqrt(size); i++) { if(array[i] == true) { for(int j = i * 2; j < size; j++) { if(j % i == 0) array[j] = false; } } } printarray(array, size); return 0; } //функция для вывода результатов работы void printarray(bool myArray, const int mySize) { int counter = 0; for(int i = 2; i < mySize; i++) { if(myArray[i] == true) { cout << i << endl; counter++; } } //выводим общее количество найденных простых чисел cout << endl << "Total: " << counter << endl; }

نتيجة البرنامج: (تم العثور على 168 عدد أولي)

6. في الفقرة الخامسة تم توضيح الطريقة الأولى لتطبيق خوارزمية إيجاد الأعداد الأولية. أوجه انتباهكم إلى الطريقة الثانية، حيث لن يحتوي المصفوفة على قيم منطقية (صواب / خطأ)، ولكن قيم الأعداد الصحيحة التي "سنغربلها" على منخل إراتوستينس. أولئك. مبدأ تشغيل الخوارزمية هو نفسه، فقط التنفيذ يختلف قليلاً. ربما سوف يعجبك هذا التنفيذ أكثر من التطبيق السابق، انظر إلى الكود

خوارزمية للعثور على الأعداد الأولية - غربال إراتوستينس في لغة C++. الطريقة الثانية

// غربال إراتوستينس #include باطلة SimplePrint(int, const int); استخدام اسم للمحطة؛ int main() ( const int size = 100; int array; for(int k = 0; k< size; k++) array[k] = k; array = 0; for(int i = 2; i < sqrt(size); i++) { if(array[i] != 0) { for(int j = i * 2; j < size; j += i) { array[j] = 0; } } } simplePrint(array, size); return 0; } void simplePrint(int array, const int size) { for(int i = 0; i < size; i++) if(array[i] != 0) cout << array[i] << endl; }

في هذا التنفيذ، نعطي أيضًا قيمًا أولية للمصفوفة، ولكن ليست منطقية، بل رقمية (0، 1، 2، 3، 4، 5 ...). هذه القيم العددية ستكون هي الأرقام التي "سنغربلها" على منخل إراتوستينس. اضبط القيم بهذا الرمز

من أجل (int k = 0؛ k< sqrt(size); k++) array[k] = k;

سنضع علامة على الأعداد التي ليست أعدادًا أولية على أنها صفر. نحن نعلم أن الرقمين 0 و1 ليسا أرقامًا أولية، لذا يمكن تمييزهما على الفور كأصفار: الخلية الأولى من المصفوفة هي صفر بالفعل، لكن الخلية الثانية التي تحتوي على واحد تحتاج إلى التغيير

من أجل (int i = 2؛ i< sqrt(size); i++) { if(array[i] != 0) { for(int j = i * 2; j < size; j += i) { array[j] = 0; } } }

دعونا نحلل التكرار الأول: i = 2. تم استيفاء شرط if، لأن تحتوي خليتنا الثانية على القيمة 2، ونذهب إلى الحلقة الداخلية التي ستقوم "بغربلة" الأرقام. بعد فحص الكود، نرى أن جميع قيم المصفوفة التي هي مضاعفات العددين (4، 6، 8، 10، 12، وهكذا) قد تغيرت (تم وضع علامة عليها) إلى الصفر. في التكرار التالي، سيحدث نفس الشيء، ولكن مع الخطوة 3، يتم تحديد القيم إلى الصفر (6، 9، 12، 15، 18، وهكذا).

بعد اكتمال خوارزمية البحث عن الأعداد الأولية، نقوم بعرض قيم عناصر المصفوفة التي لا تساوي الصفر على الشاشة. ستكون هذه هي الأعداد الأولية التي تم العثور عليها

من أجل (int i = 0؛ i< size; i++) if(array[i] != 0) cout << array[i] << endl;

7. إذا رغبت في ذلك، يمكنك، سواء في التطبيق الأول أو في التطبيق الثاني، جمع القيم الموجودة للأعداد الأولية في مصفوفة جديدة، والتي سنقوم بإنشائها ديناميكيًا. للقيام بذلك، تحتاج إلى تغيير رمز الوظيفة التي تطبع نتائج الخوارزمية قليلاً. هنا هو الكود الناتج

// دالة لإخراج نتائج العمل void printarray(bool myArray, const int mySize) ( int counter = 0; // احسب عدد الأعداد الأولية التي تم العثور عليها for(int i = 2; i< mySize; i++) if(myArray[i] == true) counter++; //выводим общее количество найденных простых чисел cout << endl << "Total: " << counter << endl << endl; //динамически создаем массив нужного размера int *simple = new int; //заполняем созданный массив простыми числами for(int i = 2, k = 0; i < mySize; i++) if(myArray[i] == true) simple = i; //выводим содержимое на экран for(int i = 0; i < counter; i++) cout << simple[i] << endl; }

نعلن عن عداد يحسب عدد الأعداد الأولية الموجودة. بعد ذلك، بمعرفة عددها، يمكننا إنشاء مصفوفة ديناميكيًا وملئها بالأعداد الأولية. في نهاية الدالة، نعرض محتوياتها على الشاشة، وبالتالي نعرض قائمة بالقيم التي تم العثور عليها والموجودة في النطاق من 0 إلى 1000.

لذلك، قمنا بالاطلاع على خوارزمية العثور على الأعداد الأولية، وعلى وجه الخصوص، استخدمنا "منخل إراتوستينس" لهذا الغرض. يمكن طرح جميع الأسئلة حول الخوارزمية في المنتدى أو في التعليقات.

مقالات مماثلة