أفضل خوارزمية معروفة للعثور على جميع الأعداد الأولية التي لا تزيد عن واحدة معينة هي منخل إراتوستينس . إنه يعمل بشكل رائع للأرقام التي تصل إلى مليارات ، ربما يصل إلى عشرات المليارات ، إذا تمت كتابتها بدقة. ومع ذلك ، فإن كل من يحب المرح مع الأعداد الأولية يعرف أنك تريد دائمًا الحصول على أكبر عدد ممكن من الأشخاص. ذات مرة ، لحل مشكلة واحدة على الهاكرانك ، كنت بحاجة إلى قاعدة بيانات في الذاكرة من الأعداد الأولية تصل إلى مائة مليار. مع أقصى قدر من تحسين الذاكرة ، إذا كنت تمثل الأرقام الفردية في منخل إراتوستينس بمصفوفة صغيرة ، فسيكون حجمها حوالي 6 غيغابايت ، والتي لا تتناسب مع ذاكرة الكمبيوتر المحمول الخاص بي. هناك تعديل للخوارزمية أقل تطلبًا بكثير في الذاكرة (تقسيم النطاق الأصلي للأرقام إلى عدة قطع ومعالجة قطعة واحدة في كل مرة) -منخل إراتوستينس المجزأ ، ولكن من الصعب تنفيذه ، ولن تتناسب النتيجة بأكملها مع الذاكرة على أي حال. أدناه ، استرعي انتباهك إلى خوارزمية بسيطة تقريبًا مثل منخل إراتوستينس ، ولكنها تعطي تحسينًا مزدوجًا عن طريق الذاكرة (أي أن قاعدة بيانات من الأعداد الأولية تصل إلى مائة مليار ستشغل حوالي 3 غيغابايت ، والتي يجب أن تتناسب بالفعل مع ذاكرة الكمبيوتر المحمول القياسي).أولاً ، لنتذكر كيف يعمل منخل إراتوستينس: في مجموعة من الأرقام من 1 إلى N ، يتم شطب الأرقام القابلة للقسمة على اثنين ، ثم يتم تقسيم الأرقام على 3 ، وهكذا. ستكون الأرقام المتبقية بعد الشطب بسيطة:2 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19 . 21 . 23 . 25 . 27 . 29 ...
2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . 25 . . . 29 ...
2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 ...
كود C #class EratospheneSieve
{
private bool[] Data;
public EratospheneSieve(int length)
{
Data = new bool[length];
for (int i = 2; i < Data.Length; i++) Data[i] = true;
for (int i = 2; i * i < Length; i++)
{
if (!Data[i]) continue;
for (int d = i * i; d < Length; d += i) Data[d] = false;
}
}
public int Length => Data.Length;
public bool IsPrime(int n) => Data[n];
}
على جهاز الكمبيوتر المحمول الخاص بي ، يتم احتساب ما يصل إلى 15 مليار ثانية ويستهلك جيجابايت من الذاكرة.تسمى الخوارزمية التي سنستخدمها عامل العجلة . لفهم جوهرها ، نكتب الأرقام الطبيعية مع قرص من 30 قطعة متتالية: 0 1 2 3 4 5 ... 26 27 28 29
30 31 32 33 34 35 ... 56 57 58 59
60 61 62 63 64 65 ... 86 87 88 89
...
وشطب جميع الأرقام القابلة للقسمة على 2 و 3 و 5:. 1 . . . . . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29
. 31 . . . . . 37 . . . 41 . 43 . . . 47 . 49 . . . 53 . . . . . 59
. 61 . . . . . 67 . . . 71 . 73 . . . 77 . 79 . . . 83 . . . . . 89
...
يمكن ملاحظة أن الأرقام في كل صف يتم شطبها في المواضع نفسها. نظرًا لأننا شطبنا فقط الأرقام المركبة (باستثناء ، في الواقع ، الأرقام 2 ، 3 ، 5) ، فإن الأعداد الأولية يمكن أن تكون فقط في مواضع غير مميزة.نظرًا لوجود ثمانية أرقام من هذا القبيل في كل صف ، فإن هذا يعطينا فكرة تمثيل كل ثلاثين رقمًا مع بايت واحد ، كل من البتات الثمانية سيشير إلى بساطة الرقم في الموضع المقابل. هذه المصادفة ليست جميلة جمالية فحسب ، بل تبسط أيضًا إلى حد كبير تنفيذ الخوارزمية!
التنفيذ الفني
أولاً ، هدفنا هو الوصول إلى مائة مليار ، لذلك لا يمكن الاستغناء عن أربعة أرقام بايت. لذلك ، ستبدو الخوارزمية لدينا على النحو التالي:class Wheel235
{
private byte[] Data;
public Wheel235(long length)
{
...
}
public bool IsPrime(long n)
{
...
}
...
}
لسهولة التنفيذ ، سنقوم بتقريب الطول لأقرب رقم قابل للقسمة على 30. ثمclass Wheel235
{
private byte[] Data;
public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new byte[length/30];
...
}
public long Length => Data.Length * 30L;
...
}
بعد ذلك ، نحتاج إلى مصفوفتين: أحدهما يترجم الفهرس 0..29 إلى رقم البت ، والثاني ، على العكس من ذلك ، رقم البت في الموضع الثلاثين. باستخدام هذه المصفوفات وقليل من الحساب قليلا ، نقوم ببناء مراسلات واحد لواحد بين الأرقام الطبيعية والبتات في صفيف البيانات. من أجل البساطة ، نستخدم طريقتين فقط: IsPrime (n) ، والذي يسمح لك بمعرفة ما إذا كان الرقم أوليًا ، و ClearPrime (n) ، الذي يضبط البت المقابل إلى 0 ، مع وضع علامة على الرقم n كمركب:class Wheel235
{
private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };
private static int[] INDEX_TO_BIT = new int[] {
-1, 0,
-1, -1, -1, -1, -1, 1,
-1, -1, -1, 2,
-1, 3,
-1, -1, -1, 4,
-1, 5,
-1, -1, -1, 6,
-1, -1, -1, -1, -1, 7,
};
private byte[] Data;
...
public bool IsPrime(long n)
{
if (n <= 5) return n == 2 || n == 3 || n == 5;
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return false;
return (Data[n / 30] & (1 << bit)) != 0;
}
private void ClearPrime(long n)
{
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return;
Data[n / 30] &= (byte)~(1 << bit);
}
}
لاحظ أنه إذا كان الرقم قابلاً للقسمة على 2 أو 3 أو 5 ، فإن رقم البت سيكون -1 ، مما يعني أن الرقم مركب بوضوح. حسنًا ، وبالطبع ، نقوم بمعالجة حالة خاصة n <= 5.الآن ، في الواقع ، الخوارزمية نفسها ، والتي تكرر حرفياً غربال إراتوستينس: public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new byte[length / 30];
for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
}
تبعا لذلك ، فإن الطبقة الناتجة كلها:يبدو مثل هذاclass Wheel235
{
private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };
private static int[] INDEX_TO_BIT = new int[] {
-1, 0,
-1, -1, -1, -1, -1, 1,
-1, -1, -1, 2,
-1, 3,
-1, -1, -1, 4,
-1, 5,
-1, -1, -1, 6,
-1, -1, -1, -1, -1, 7,
};
private byte[] Data;
public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new byte[length / 30];
for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
}
public long Length => Data.Length * 30L;
public bool IsPrime(long n)
{
if (n >= Length) throw new ArgumentException("Number too big");
if (n <= 5) return n == 2 || n == 3 || n == 5;
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return false;
return (Data[n / 30] & (1 << bit)) != 0;
}
private void ClearPrime(long n)
{
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return;
Data[n / 30] &= (byte)~(1 << bit);
}
}
هناك مشكلة صغيرة واحدة فقط: لا يعمل هذا الرمز للأرقام الأكبر من حوالي 65 مليار! عند محاولة بدء تشغيله بمثل هذه الأرقام ، يتعطل البرنامج بخطأ:Unhandled Exception: System.OverflowException: Array dimensions exceeded supported range.
تكمن المشكلة في أنه لا يمكن أن تحتوي الصفيفات c # على أكثر من 2 ^ 31 عنصرًا (على ما يبدو لأن التنفيذ الداخلي يستخدم فهرس صفيف رباعي بايت). أحد الخيارات هو ، على سبيل المثال ، إنشاء مصفوفة طويلة [] بدلاً من صفيف بايت [] ، ولكن هذا سيعقد الحساب قليلاً قليلاً. من أجل البساطة ، سنذهب في الاتجاه الآخر ، وننشئ فئة خاصة تحاكي المصفوفة المطلوبة ، وتحمل صفيفين قصيرين في الداخل. في الوقت نفسه ، سنمنحه الفرصة لننقذ أنفسنا على القرص حتى تتمكن من حساب الأعداد الأولية مرة واحدة ، ثم استخدام قاعدة البيانات مرة أخرى: class LongArray
{
const long MAX_CHUNK_LENGTH = 2_000_000_000L;
private byte[] firstBuffer;
private byte[] secondBuffer;
public LongArray(long length)
{
firstBuffer = new byte[Math.Min(MAX_CHUNK_LENGTH, length)];
if (length > MAX_CHUNK_LENGTH) secondBuffer = new byte[length - MAX_CHUNK_LENGTH];
}
public LongArray(string file)
{
...
}
public long Length => firstBuffer.LongLength + (secondBuffer == null ? 0 : secondBuffer.LongLength);
public byte this[long index]
{
get => index < MAX_CHUNK_LENGTH ? firstBuffer[index] : secondBuffer[index - MAX_CHUNK_LENGTH];
set
{
if (index < MAX_CHUNK_LENGTH) firstBuffer[index] = value;
else secondBuffer[index - MAX_CHUNK_LENGTH] = value;
}
}
public void Save(string file)
{
...
}
}
أخيرًا ، اجمع كل الخطواتالنسخة النهائية من الخوارزميةclass Wheel235
{
class LongArray
{
const long MAX_CHUNK_LENGTH = 2_000_000_000L;
private byte[] firstBuffer;
private byte[] secondBuffer;
public LongArray(long length)
{
firstBuffer = new byte[Math.Min(MAX_CHUNK_LENGTH, length)];
if (length > MAX_CHUNK_LENGTH) secondBuffer = new byte[length - MAX_CHUNK_LENGTH];
}
public LongArray(string file)
{
using(FileStream stream = File.OpenRead(file))
{
long length = stream.Length;
firstBuffer = new byte[Math.Min(MAX_CHUNK_LENGTH, length)];
if (length > MAX_CHUNK_LENGTH) secondBuffer = new byte[length - MAX_CHUNK_LENGTH];
stream.Read(firstBuffer, 0, firstBuffer.Length);
if(secondBuffer != null) stream.Read(secondBuffer, 0, secondBuffer.Length);
}
}
public long Length => firstBuffer.LongLength + (secondBuffer == null ? 0 : secondBuffer.LongLength);
public byte this[long index]
{
get => index < MAX_CHUNK_LENGTH ? firstBuffer[index] : secondBuffer[index - MAX_CHUNK_LENGTH];
set
{
if (index < MAX_CHUNK_LENGTH) firstBuffer[index] = value;
else secondBuffer[index - MAX_CHUNK_LENGTH] = value;
}
}
public void Save(string file)
{
using(FileStream stream = File.OpenWrite(file))
{
stream.Write(firstBuffer, 0, firstBuffer.Length);
if (secondBuffer != null) stream.Write(secondBuffer, 0, secondBuffer.Length);
}
}
}
private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };
private static int[] INDEX_TO_BIT = new int[] {
-1, 0,
-1, -1, -1, -1, -1, 1,
-1, -1, -1, 2,
-1, 3,
-1, -1, -1, 4,
-1, 5,
-1, -1, -1, 6,
-1, -1, -1, -1, -1, 7,
};
private LongArray Data;
public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new LongArray(length / 30);
for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
}
public Wheel235(string file)
{
Data = new LongArray(file);
}
public void Save(string file) => Data.Save(file);
public long Length => Data.Length * 30L;
public bool IsPrime(long n)
{
if (n >= Length) throw new ArgumentException("Number too big");
if (n <= 5) return n == 2 || n == 3 || n == 5;
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return false;
return (Data[n / 30] & (1 << bit)) != 0;
}
private void ClearPrime(long n)
{
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return;
Data[n / 30] &= (byte)~(1 << bit);
}
}
ونتيجة لذلك ، حصلنا على فصل يمكنه حساب الأعداد الأولية التي لا تتجاوز مائة مليار وحفظ النتيجة على القرص (كان لدي هذا الرمز على جهاز الكمبيوتر المحمول لمدة 50 دقيقة ؛ كان حجم الملف الذي تم إنشاؤه حوالي 3 غيغابايت ، كما هو متوقع): long N = 100_000_000_000L;
Wheel235 wheel = new Wheel235(N);
wheel.Save("./primes.dat");
ثم اقرأ من القرص واستخدم: DateTime start = DateTime.UtcNow;
Wheel235 loaded = new Wheel235("./primes.dat");
DateTime end = DateTime.UtcNow;
Console.WriteLine($"Database of prime numbers up to {loaded.Length:N0} loaded from file to memory in {end - start}");
long number = 98_000_000_093L;
Console.WriteLine($"{number:N0} is {(loaded.IsPrime(number) ? "prime" : "not prime")}!");