مرجع
آخر الزيارات

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

200 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: غربال إراتوستينس هي خوارزمية بسيطة لإيجاد جميع الأعداد الأولية حتى عدد ما. تتناول المقالة 4 أقسام، منها «غربال أويلر»، «البرمجة» و«وصف الخوارزمية».
المحتويات
  1. غربال أويلر
  2. البرمجة
  3. وصف الخوارزمية
  4. A[j] = false
غربال إراتوستينس

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

غربال أويلر

  • انظر برهان صيغة جداء أويلر بالنسبة لدالة زيتا لريمان.
  • انظر كذلك
  • غربال أتكين

البرمجة

  • المدخل: عدد n طبيعي أكبر قطعا من 1
  • ليكن A جدولا من القيم البوليانية، مفهرسا بالأعداد الطبيعية من
  • 2 حتى n، كلها تساوي في البداية ل true.
  • for i = 2, 3, 4, ...
  • , while i ≤ n/2:
  • if A[i] is true:
  • for j = 2i, 3i, 4i, ..., while j ≤ n:

وصف الخوارزمية

  • لإيجاد الأعداد الأولية الأصغر من n تتبع الخوارزمية الخطوات التالية:
  • أنشئ قائمة بجميع الأعداد من الرقم 2 إلى العدد الذي تريد,
  • نبدأ بقيمة ل p تساوي 2، أول الأعداد الأولية,
  • اشطب من القائمة جميع الأعداد من مضاعفات p والتي هي أكبر من p,

كرر الخطوات 3 و4 حتى يصير p2 هي أكبر من n,

وفي السياق ذاته، ابحث عن العدد التالي غير المشطوب في القائمة، هذا العدد هو العدد الأولي التالي، وسيكون هو العدد p التالي,

جميع الأعداد الباقية على القائمة هي أعداد أولية.

A[j] = false

الآن كل الأعداد i حيث [A[i تساوي true هي أعداد أولية.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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