سونداراما غربال

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

Sundarama غربال هي واحدة من ثلاث طرق الأكثر شهرة لتوليد الأعداد الأولية. من المعتاد الآن أن نعاملها كأشياء غريبة بسبب التعقيد الحسابي الضعيف: O (N (logN)). ومع ذلك ، فإن المقاربين هم مقاربون ، وفي الممارسة ، في نطاق النخل 32 بت ، Atkin ، على سبيل المثال ، لا يتفوق على Sundaram إلا بتحسين دقيق.

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

يجد Sundarama غربال جميع الأعداد الأولية في مجموعة معينة من الأعداد الطبيعية 3 ≤ n ≤ N "غربلة" المكونات. دون فقدان العمومية ، يمكن اعتبار قيمة N غريبة. إذا كان N متساويًا ، فيُضمن أن يكون مركبًا ، ويمكن استبعاده من نطاق الغربلة عن طريق تقليل قيمة الحد العلوي بواحد.

تستند الخوارزمية إلى الحقيقة التالية. يمكن تمثيل أي رقم فردي مركب n كمنتج يتكون من رقمين فرديين طبيعيين أكبر من واحد:

(1) n = (2 * i + 1) * (2 * j + 1) ،

حيث i و j أرقام طبيعية (صفر ليس رقمًا طبيعيًا). من المستحيل تخيل رقم أولي n في هذا النموذج ، لأنه بخلاف ذلك سيعني أن هناك مقسومات إضافية بجانب نفسه والرقم.

نكتب odd في النموذج 2 * m + 1 ، نستبدلها في (1) ، ونحصل على التعبير m:

(2) م = 2 * i * j + i + j.

هذا التحول يؤدي مباشرة إلى فكرة غربال Sundaram.

من أجل التخلص من الأرقام المركبة من فاصل زمني معين ، يجب عليك استخدام صفيف يكون فيه العنصر مع الفهرس m ممثلاً للرقم 2 * m + 1. بعد تنظيم تعداد قيم المتغيرات i و j ، سنحسب الفهرس m بالصيغة (2) ، وفي المقابل تعيين عناصر مجموعة علامة "رقم مركب". بعد اكتمال التعداد ، سيتم تمييز جميع الأرقام المركبة في النطاق ، ويمكن اختيار الأعداد الأولية من خلال عدم وجود علامة.

يبقى لتوضيح التفاصيل الفنية.

استنادًا إلى المنطق السابق ، لتمثيل الحد العلوي (الفردي) لنطاق الغربلة N ، يفترض الفهرس m قيمته القصوى mmax = (N - 1) / 2. هذا يحدد الحجم المطلوب للصفيف.

سنقوم بتعداد قيم i و j في دورتين: حلقة خارجية لتعداد قيم i ، وحلقة داخلية متداخلة لقيم j.

القيمة الأولية لعداد الحلقة الخارجية هي i = 1. نظرًا للتماثل الكامل لحدوث المتغيرين i و j في التعبير (2) ، لتجنب العمليات الحسابية المكررة المتكررة ، يجب أن تبدأ الدورة الداخلية بالقيمة j = i.

ابحث عن الحد الأقصى لقيمة عداد الحلقة الخارجية imax ≥ i. إذا كانت حدود النطاق N عبارة عن رقم مركب فردي ، فمع القيمة i = imax ، يجب تنفيذ الحلقة الداخلية مرة واحدة على الأقل بقيمة المعلمة j = imax لحذف N ، وسيستغرق التعبير (2) قيمته القصوى:

mmax = 2 * imax * imax + imax + imax ،
imax ^ 2 + imax - mmax / 2 = 0.

لحل هذه المعادلة التربيعية ، نحصل على: imax = (√ (2 * mmax + 1) -1) / 2 = (√N-1) / 2.
تم العثور على التقييد الخاص بعداد الدورة الداخلية jmax ≥ j من عدم المساواة
mmax ≥ 2 * i * j + i + j ، حيث نحصل على: jmax = (mmax - i) / (2 * i + 1).

يجب تقريب قيم الحدود العليا إلى أقرب قيمة كاملة ، مع تجاهل الجزء الكسري.

فيما يلي قائمة بفئة C # Sundaram بسيطة جدًا تنفذ الطريقة الموضحة.

using System; using System.Collections; namespace CSh_Sundaram { public class Sundaram { public double dt; //   () private long t1; //   private long t2; //   private uint limit; //     private int arrlength; //   private BitArray Prim; //    private int counter; public Sundaram(uint _limit) { limit = _limit; if (limit % 2 == 0) limit -= 1; arrlength = (int)(limit / 2); Prim = new BitArray(arrlength); t1 = DateTime.Now.Ticks; Sieve(); //  t2 = DateTime.Now.Ticks; dt = (double)(t2 - t1) / 10000000D; counter = -1; } public uint NextPrime { get { while (counter < arrlength - 1) { counter++; if (!Prim[counter]) return (uint)(2 * counter + 3); } return 0; } } private void Sieve() { int imax = ((int)Math.Sqrt(limit) - 1) / 2; for (int i = 1; i <= imax; i++) { int jmax = (arrlength - i) / (2 * i + 1); for (int j = i; j <= jmax; j++) { Prim[2 * i * j + i + j - 1] = true; } } } } } 

كمعلمة عند إنشاء كائن من نوع Sundaram ، تتم الإشارة إلى الحد الأعلى لنطاق الغربلة. لغربلة ، يستخدم الفصل صفيف نوع BitArray. يؤدي ذلك إلى زيادة وقت التشغيل ، ولكنه يسمح لك بتغطية نطاق 32 بت بالكامل من نوع uint. يتم إجراء غربلة عند الوصول إلى أسلوب Sieve () من مُنشئ الفصل الدراسي. بعد اكتماله ، سيحتوي الحقل dt على وقت تنفيذ Sieve بالثواني.

عند الوصول إلى خاصية NextPrime ، بالتتابع ، بدءًا من 3 ، بترتيب تصاعدي ، سيتم إرجاع الأعداد الأولية. بعد استنفاد جميع العناصر البسيطة من النطاق ، سيتم إرجاع القيمة 0.