خوارزمية الأعداد الأولية

أظن أنك ستغيّر رأيك بعد الاطّلاع على هذه الصفحة

إلا إن كنت تنوي حفظ ما يزيد عن 234,057,667,276,344,607 عدد أولي :(

إذا كنت تريد تخزين قيم الأعداد الأولية للقيام بـ hashing  فأظن أن اختبارات primality tests سريعة على أرقام كبيرة ستكون مفيدة أكثر

وفقك الله

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

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

شكرا لك.

و الله ولي التوفيق

حتى لو كنت ستخزّن كل عدد في بت واحد فستحتاج ما يزيد عن 26609 تيرا بايت ... صدقني أن فكرة التخزين غير عمليّة

بالنسبة لاختبار الأعداد الأولية ..

اختبار باقي القسمة يحتاج إلى( sqrt(n  عملية اختبار ( ويمكنك الاختبار على الأعداد الأولية الأصغر من جذر العدد ولكن هذا لا يقدّم الكثير من التحسين )

المهم .. هناك خوارزمية تستغرق( log(n واسمها Fermat last theorem  ولكنها اختبار تقريبي ( نسبة نجاحه تفوق 99% ) طريقته بسيطة جداً .. حاولت تلخيصها هنا 

وحسب ما أعرف فأحدث خوارزمية (غير تقريبية) اسمها miller-rabin وهي تعتمد على fermat last theorem

يمكنك استخدام اختبار باقي القسمة على الأعداد (المحتمل كونها أولية) حسب الاختبار السابق

في python يمكنك استخدام التابع pow للقيام باختبار fermat حيث يقوم بـmodular exponentation وهذا كود سريع ,

اختبار fermat بدون pow

الشرط التالي

2**(t-1)%t==1

باستخدام pow

pow(2,a-1,a)==1

يمكنك استبدال 2 بأي عدد آخر بشرط أن يكون 2, a عددان أوليان بالنسبة لبعضهما coprime (يعني القاسم المشترك بينهما 1 )

وفقك الله

الطريقة المحسّنة قليلاً المذكورة في الرد السابق

اقتباس

( ويمكنك الاختبار على الأعداد الأولية الأصغر من جذر العدد ولكن هذا لا يقدّم الكثير من التحسين )

أعني بها ما يلي :

طالما أنك تحفظ الأعداد الأولية فيمكنك اختبار باقي القسمة على الأعداد الأولية فقط .. فمثلاً لا داعي لاختبار باقي القسمة على 15 إن كان العدد تم اختباره على 3 و 5 ..

أظن أن رد الأخ حسام هنا سيفيدك بإذن الله

وفقك الله

اقتباس

صدقني أن فكرة التخزين غير عمليّة

معك حق لو اردت تخزين ألف مليار عدد اولي كل واحد بمساحة 8 بايت فأستحاج عدد ضخم من المساحة و لكن تخيل انك تقوم بحفظ الموقع من رقم معين فمثلا سأقوم بتقسيم الأعداد الاولية إلى مجموعة ثابته تتألف من 65535 رقم و ساقوم بتحديد أكبر رقم في كل مجموعه ثم سأقوم بحفظ الفرق بين هذا الرقم و ما قبله (أى offset) و عندما اريد الحصول على العدد الأولي رقم مليار كل ما ساحتاجه هو الوصول للموقع الموجود فيه و من ثم إجراء العملية الحسابية التى اريدها و أحصل عليه.

بهذه الطريقة قمت بحفظ كافة الأعداد الأولية فى مدى 32بت داخل 250 ميجا فقط و كانت فى الأصل تخزن فى 750 ميجا و طبعا هذه الـ 250 ميجا تحتوى على الـ offset بكامل مساحته بمعنى لم اقم بحذف الأصفار منها.

عموما حتى لو قمت بترك الفكره و وجدت بديل فالموضوع نفسه يشغلنى لعلي احتاجه فى أمر أخر.

=====================

لقد راجعت المشاركة و رابط SO قراته من قبل و مشكلته انك لا تستطيع استخدام SoE أو SoA فى مدى محدد

اقتباس

طالما أنك تحفظ الأعداد الأولية فيمكنك اختبار باقي القسمة على الأعداد الأولية فقط .. فمثلاً لا داعي لاختبار باقي القسمة على 15 إن كان العدد تم اختباره على 3 و 5 ..

و هذا هو أحد مزايا وجود الأعداد الأولية فى مدى 32بت و لكن أختبار باقي القسمه نفسه بطيء، فهل توجد لديك اى افكار اخرى

و الله ولي التوفيق

اختبار fermat الذي تحدثت عنه في هذا الرد 

يقوم بعملية باقي القسمة مرة واحدة فقط ..  ( على الأقل )

وكلما زدت العمليات يكون أدق ..

إذا لم يكن لديك مشكلة في التخزين , يمكنك القيام بغربلة eratothenis على مستوى البت (لا بد أنك فكرت بها من قبل)

مثلاً لديك الأعداد من 1 إلى 8 كما يلي (من اليسار لليمين ) 01101010  (البت = هل العدد أولي ) , ويبقى عليك حفظ عدد الأعداد الأولية التي تقع قبل البت رقم كذا لتسريع الوصول ..

الغربلة سريعة جداً مقارنة بأي خوارزمية أخرى , أعتقد أنك سترسو على اختيارها ..  وهناك طرق لتسريع الغربلة تعتمد تجاوز مضاعفات الأعداد الصغيرة مثل 2-3-5-7 وهكذا .. كنت قد كتبت بعض الأكواد عنها سابقاً يمكنني البحث عنها إن أردت

وفقك الله

اقتباس

إذا لم يكن لديك مشكلة في التخزين , يمكنك القيام بغربلة eratothenis على مستوى البت (لا بد أنك فكرت بها من قبل)

مثلاً لديك الأعداد من 1 إلى 8 كما يلي (من اليسار لليمين ) 01101010  (البت = هل العدد أولي ) , ويبقى عليك حفظ عدد الأعداد الأولية التي تقع قبل البت رقم كذا لتسريع الوصول ..

الغربلة سريعة جداً مقارنة بأي خوارزمية أخرى , أعتقد أنك سترسو على اختيارها ..  وهناك طرق لتسريع الغربلة تعتمد تجاوز مضاعفات الأعداد الصغيرة مثل 2-3-5-7 وهكذا .. كنت قد كتبت بعض الأكواد عنها سابقاً يمكنني البحث عنها إن أردت

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

ما تقول غير واضح لي، هل يمكنك التوضيح أكثر.

شكرا لك.

و الله ولي التوفيق

بارك الله فيك

سأشرح فكرة الغربلة التي تحدثت عنها , أرجو أن تكون مفيدة لك

الأجزاء التالية من كود كتبته منذ عام تقريباً .. لكنه dirty بشكل مزعج ..

الكود يقوم بإيجاد الأعداد الأولية الأصغر من مليار في أقل من دقيقة

بدايةً أحفظ الأعداد الأولية الأصغر من جذر المليار لإيجاد جميع الأعداد الأولية حتى المليار

for(unsigned int i=3;primes[3402]==0;i+=2)
    {for(unsigned int j=0;i>primes[j]*primes[j]&&i%primes[j]!=0;j++);
        if(i<primes[j]*primes[j]){index++;primes[index]=i;}}

فيما يلي شرح ما أتذكره من الكود :D

المصفوفة Numbers تحفظ حالة جميع الأعداد حتى مليار .. (الحالة = أولي أو لا ) وذلك في بت واحد لكل عدد

نعتبر جميع الأعداد أولية في البداية

unsigned char *Numbers=new unsigned char[1000000000/8];
    for(int A=0;A<1000000000/8;A++)
        Numbers[A]=0xFF;

مثلاً Numbers[0]=53; فيمكنك فهمها عند التحويل إلى binary

=================

العدد 9699690 هو المضاعف المشترك الأكبر للأعداد 2-3-5-7-11-13-17-19

وهذا يعني أن إيجاد حالة الأعداد في مجال من 0 إلى 9699690 هو نفسه من 9699690 إلى 9699690*2 وهكذا .. من 9699690*2 إلى 9699690*3  إلخ

وبذلك نقوم بالتخلص من اختبارات 2-3-5-7-11-13-17-19 على مليار عدد من خلال9699690 عدداً فقط ..

unsigned char *numbers=new unsigned char[9699690];
    for(unsigned int i1=0;i1<9699690;i1++)
        numbers[i1]=(i1%2)&&(i1%3)&&(i1%5)&&(i1%7)&&(i1%11)&&(i1%13)&&(i1%17)&&(i1%19);

والآن ما عليك سوى نسخ حالة الأعداد من 0 إلى 9699690 إلى المصفوفة Numbers  وكما ذكرت هذه العملية تقوم بالغربلة على أقل من 10 مليون عدد , ويمكن نسخ نتيجتها على الأعداد إلى اللانهاية (أنا اخترعتها p: ولكن أشك في كوني الوحيد) 

وتوفّر غربلة مضاعفات الأعداد الأولية 2-3-5-7-11-13-17-19

(طبعاً يمكن تطويرها لتشمل 23 و 29 وإلخ إلخ .. ولكن هذا غير مفيد في مثالنا البسيط (للأعداد أقل من مليار)

====================

والآن يبقى غربلة مضاعفات الأعداد الأولية الأكبر من 19 (بدءا من 23 )

for(i=8;i<3403;i++)        for(unsigned int j=primes*primes;j<1000000000;j+=primes)            Numbers[j/8]&=putzero[j%8];

المصفوفتان putzero و putone لتسريع العمليات على البتات بشكل ليس له مثيل

char putzero[8]={127,-65,-33,-17,-9,-5,-3,-2};
    char putone[8]={-128,64,32,16,8,4,2,1};

أظن أن استخدامها واضح فقط اعمل & وحدد عنصر المصفوفة فهو يمثّل رقم البت

إذا كان هناك نقاط غير واضحة أرجو منك السؤال عنها ..

بارك الله فيك ووفقك ..

بانتظارك

لان ادخل في كلام العمالقة في جمع الأعداد أولية

ولكن كلامي يمكن يفيد في تقليل المساعة فكرة صديق قديدم مف البرمجة عي تعتمد علي تحويل الارقام الي حروف مثل رقم 903 يحول Z3 وهذ بعد تقسيمه رقمين في كل مجموعة وتحويله كفكره الي hex ابطء بعض الشيءولكن اقل مساحة

أخ كريم أهلاً بك :)

تحويل الأعداد إلى نظام 36 أو حتى أحياناً إلى 64 أو حتى يمكنك الوصول إلى 94 يوفّر المساحة بشكل كبير

ولكن الأخ C++er قد تحاوز هذه الحدود بشكل كبير , فهو كما ذكر .. يتعامل مع البتات بشكل مباشر بحيث يوفّر مساحة أكبر من طريقة التحويل لأنظمة عد كبيرة , بشكل كبير

شكراً لك ,

بالتوفيق

قمت بوضع السؤال بموقع SO و وجدت الإجابة.

و الله ولي التوفيق

بالنسبة لموضوع حفظ الأعداد الاولية، إليكم الأتي:
 
الأعداد الأولية فى مدى 32بت عددهم 203,280,221 و إذا اردنا حفظهم داخل ملف سنحتاج إلي 4 بايت لكل عدد و هذا سيعطينا:
 

203280221 * 4 = 813120884 bytes = 775 MB

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

203280221 / 65537 = 3101203280221 % 65537 = 49984

و بهذا نعلم أن لدينا 3101 مجموعة مكونة من 65536 عنصر و كل منهم بمساحة 2 بايت و لدينا الرقم أساس المجموعة بمساحة 4 بايت.
أيضا لدينا عدد 49983 عدد أولي بمساحة 2 بايت و الرقم الأساس بمساحة 4 بايت، لذا تصبح النتيجه:

203280221 / 65537 = 3101
203280221 % 65537 = 49984

(3101 * 65536 * 2) + (65536 * 4) + (49983 * 2) + 4
406454272 + 262144 + 99966 + 4
406816386 bytes = 388 MB

المساحة الجديدة تعادل نصف المساحة الأصلية، الأن لنجرب جعل كل مجموعة مؤلفة من 256 عدد بدلا من 65536.

203280221 / 257 = 790973
203280221 % 257 = 160

(790973 * 256) + (256 * 4) + 159 + 4
202489088 + 1024 + 159 + 4
202490275 bytes = 193 MB

المساحة الجديدة أقل من ربع المساحة الأصلية بفرق ضئيل، ولكن حتى بإستخدام هذا الإسلوب فالأعداد الاولية فى مدى 64بت تحتاج 25 بيتا بايت من أصل 167 بيتا بايت و لا اعتقد انها مساحة متوفرة على الأقل ليس لي.

أول 1,248,000,000 عدد أولي يستهلك مساحة 64بت يحتاج إلى 9.30 جيجا بايت للحفظ بشكل كامل و بإستخدم الإسلوب الأخير فى الحفظ نحتاج 1.19 جيجا بايت فقط و هذا أقل من ربع المساحة الأصلية بشكل كبير (الفرق 1.14 جيجا)

خلاصة القول: كلما قلت مساحة الـ offset و زاد عدد العناصر بالمجموعة كلما قلت المساحة بشكل ملحوظ و لكن ستجد امامك معضله كبيرة وهي أنه أحيانا ستجد ان الفرق بين العدد الأولي الذى تريد الحصول على موقعه أكبر من مساحة الـ offset التى تستخدمها و فى هذه الحالة ستحتاج لإضافة قيمة الـ offset لهذه القيمه و إن فعلت فهذا يعنى انك يمكنك زيادة عدد العناصر داخل المجموعة من 256 إلى ما يقرب لـ 348 و هذا سيجعل المساحة الجديدة أقل من 1/6 من المساحة الأصلية و فى حالة المثال السابق سيصبح بدلا من 1.19 جيجا ستكون 950 ميجا.

هذا ما لدى فى هذا الموضوع، فإذا كان لديك تعديل من شانه تحسينها أو فكرة أفضل فشاركنا بها

و الله ولي التوفيق

لدي فكرة ولكن لم أجربها من قبل .. ومن شأنها تحسين المساحة ربما إلى النصف

عندما تكتب 11فأنت تعني 11 بالتحديد

ولكن لماذا لا نكتب 5 للدلالة على أنه الرقم الفردي الخامس (فلا نحتاج الأرقام الزوجية في حساباتنا )

وبهذا يمكنك مثلاً فعل ما يلي

أنت تأخذ الفارق بين عددين الأوليين وتخزّنه أليس كذلك ؟ مثلاً الأساس هو 3وتريد تخزين 97  عندها ستخزن 94 في جدولك .. والفكرة التي أطرحها هي أن تخزن 47

يمكنك أخذ الفارق وتخزين نصفه لأنه سيكون زوجياً دوماً , طالما أن الأساس فردي

فما رأيك ؟ الفكرة قد تنقص بت واحد لكل عدد

سؤال استفهامي : ظانت لا تريد أخذ الـ offset بين كل عدد والذي قبله حتى لا تضطر للمرور على جميع الأعداد من 2 إلى العدد المطلوب أليس كذلك ؟

(ولكنني أكرر أن تخزين جميع الأعداد في مجال 64 بت مستحيل مهما كانت طريقة التخزين فائقة ( حتى لو خزنت كل عدد في بت واحد ..) لذلك أرجو ألا يكون هذا هو هدفك وتبحث عن الحل , لأنه مستحيل

بالتوفيق

اقتباس

فما رأيك ؟ الفكرة قد تنقص بت واحد لكل عدد

سأقوم بالبحث فيها، شكرا على الفكرة.

اقتباس

سؤال استفهامي : ظانت لا تريد أخذ الـ offset بين كل عدد والذي قبله حتى لا تضطر للمرور على جميع الأعداد من 2 إلى العدد المطلوب أليس كذلك ؟

هذا صحيح، و لكن مع فكرتي و فكرتك يمكنني وضع تصميم من شأنه إيصال المساحة المطلوبه إلى 1/8.

اقتباس

(ولكنني أكرر أن تخزين جميع الأعداد في مجال 64 بت مستحيل مهما كانت طريقة التخزين فائقة ( حتى لو خزنت كل عدد في بت واحد ..) لذلك أرجو ألا يكون هذا هو هدفك وتبحث عن الحل , لأنه مستحيل

ماذا عن 50بت، هل يمكن؟

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

الفكرة الخاصة بالـ index تشبه قليلا الموجوده بقاعدة البيانات.

و الله ولي التوفيق

اقتباس

ماذا عن 50 بت

لنفرض جدلاً أنه يمكنك حفظ كل عدد أولي في بت واحد فقط بطريقة خارقة ما :)

وحسب القانون هنا

فإذا كان لديك

279,238,341,033,925 بت (أي 31.7 تيرا بايت تقريباً)

عندها يمكنك تخزين الأعداد الأولية الأقل من 10^16 (أقل قليلاً من 2^50 )

لذلك أرى أنه من الأفضل الانتقال إلى فكرة أخرى لا تتضمن حفظ "جميع" الأعداد الأولية ,

ولكن عندي فكرة يمكنها توفير نصف المساحة  .. لماذا أحفظ 3 و 5  ثم 11 و 13 ثم 17 و 19 طالما أنها twin primes يمكنني أن أقوم بحفظ ملف خاص بها فأحفظ فيه 3 و 11 و 17 ويكون هذا الملف خاصاً بالأعداد التي تكون أولية والـ+2 لها أولي أيضاً

ثم أحفظ ملف آخر لـلأولية والـ +4 لها أولي أيضاً .. ثم +6 ثم +8 وهكذا ...

وبهذا نوفّر نصف المساحة لأننا نخزن نصف الأعداد الأولية فقط دوماً

ولكن سيبقى هناك أعداد أولية لا تنتمي لأي من المجموعات السابقة مثلاً 7 .. سنضطر لوضعها في ملف مستقل , وعدد هذه الأعداد سيحدد مقدار الفائدة من هذا الفكرة

p:

بالتوفيق

السلام عليكم 
ها تسمحون لي بمشاركة ما توصلت اليه نتيجة دراسة وتجربة اشياء على مجموعة من الاعداد الاولية
كانت دراسي قائمة على الاعداد الاولية في المدى من 3 ل 1000. فوجدت ما يلي انه دائما الفرق بين العدد الاولي والذي قبله هو عدد زوجي.(ولكن لا اعرف كيف استخدم هذه الخاصية في تحسين خوارزمية للاعداد الاولية)

وايضا عندما نقوم بحساب الفرق بين عدد اولي وجميع الاعداد الاولي التي قبله ينتج عدد زوجي.

وفي بعض الاحيان عند حساب الفرق بين عدد اولي وجميع الاعداد التي قبله ان الفرق يتكرر بشكل دوري (بحاجة لتأكد من صحتها اكثر).

وايضا بحاجة لتعميم على الاعداد الاخرى.

ملاحظة اخرى (بحاجة الى تمحيص وتدقيق) : كأنه نتج معي متسلسلة فروق اعداد تشبه توزيع الالكترونات في المستويات الفرعية

وتوزيع الالكترونات في المستويات الفرعية كتالي
 s s p s p s d p s d p s f d p s f d p
تقريبا مشابهة لهذه الطريقة.

بالتوفيق 
 

اهلا بك :)

جميع الأعداد الأولية من 3 فما فوق هي فردية وبالتالي الفرق بينها هو عدد زوجي دوماً

اقتباس

وفي بعض الاحيان عند حساب الفرق بين عدد اولي وجميع الاعداد التي قبله ان الفرق يتكرر بشكل دوري (بحاجة لتأكد من صحتها اكثر).

غير صحيحة :)

اقتباس

ملاحظة اخرى (بحاجة الى تمحيص وتدقيق) : كأنه نتج معي متسلسلة فروق اعداد تشبه توزيع الالكترونات في المستويات الفرعية

وتوزيع الالكترونات في المستويات الفرعية كتالي
 s s p s p s d p s d p s f d p s f d p
تقريبا مشابهة لهذه الطريقة.

 

أمر ملفت للنظر فعلاً 

ولكنه أيضاً غير صحيح : (للأسف ..)

3 5 7 11 13 17 19 23 29 31 37

2 2 4  2  4  2   4     6   2  6

الأعداد الأولية

s  s  p  s  p  s  p  d  s  d

توزيع الالكترونات على السويات الطاقية التي ذكرتها

s  s  p   s   p   s   d   p  s d

لكنها حركة جميلة :)

مصطفى 36a2 كتب:

أمر ملفت للنظر فعلاً 

ولكنه أيضاً غير صحيح : (للأسف ..)

3 5 7 11 13 17 19 23 29 31 37

2 2 4  2  4  2   4     6   2  6

الأعداد الأولية

s  s  p  s  p  s  p  d  s  d

توزيع الالكترونات على السويات الطاقية التي ذكرتها

s  s  p   s   p   s   d   p  s d

 

لكنها حركة جميلة :)

انا لم اقصد هنا ان الفرق بين الاعداد الاولية تطابق تماما توزيع الالكترونات على المستويات الفرعية ، ولكن ما اقصده انه يوجد تشابه من نوع ما 

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

وهنا الاعداد الاولية نفس الشيء فنحن عند تعاملنا معها دائما وابدا نفرض ان العلاقة بينها من الصعب بل من المستحيل ايجادها ، ولكن لو نظر احدهم لها بصورة بسيطة وتجريدية

لتوصل للعلاقة التي بينها