الأعداد الأولية هي أرقام لا تقبل القسمة إلا على نفسها وعلى واحد. إنها مفهوم رياضي مهم وتجد تطبيقات في مختلف المجالات ، بما في ذلك التشفير والخوارزميات.
ولكن كيف يمكنني العثور على عدد الأعداد الأولية من 1 إلى ن? هناك العديد من الخوارزميات الفعالة والسريعة التي يمكن أن تساعدك في هذه المهمة.
واحدة من هذه الخوارزميات هي "غربال إراتوستينس". تعتمد هذه الطريقة على فكرة الحذف ، بدلا من التكرار على جميع الأرقام من 1 إلى ن. يمكنك إنشاء قائمة بالأرقام من 2 إلى ن واستبعاد جميع المضاعفات بالتتابع من 2 إلى جذر ن.
نتيجة لذلك ، ستبقى الأعداد الأولية فقط من 2 إلى ن. هذه الخوارزمية لها تعقيد ا (ن سجل سجل ن) وهي واحدة من أكثر الطرق فعالية للعثور على عدد الأعداد الأولية من 1 إلى ن.
- طرق البحث عن الأعداد الأولية:
- غربال إراتوستينس
- اختبار ميلر رابين
- اختبار المزرعة
- سؤال وجواب
- كيف يمكنني العثور بسرعة على عدد الأعداد الأولية من 1 إلى ن?
- كيف تعمل خوارزمية غربال إراتوستينس?
- هل هناك طرق بديلة لحساب الأعداد الأولية?
- هل من الممكن استخدام خوارزمية غربال إراتوستينس لأعداد كبيرة?
طرق لإيجاد الأعداد الأولية:
هناك طرق مختلفة للعثور على الأعداد الأولية من 1 إلى ن. تتضمن بعض الطرق الأكثر فعالية ما يلي:
- التكرار على المقسومات: لكل رقم من 2 إلى ن ، نتحقق مما إذا كان قابلا للقسمة تماما على أي رقم من 2 إلى جذر هذا الرقم. إذا كان قابلا للقسمة ، فإن الرقم مركب ، إن لم يكن— فهو بسيط. هذه الطريقة بسيطة للغاية ، ولكنها قد تكون غير فعالة للقيم الكبيرة ن.
- غربال إراتوستينس: تعتمد هذه الطريقة على فكرة إزالة جميع الأرقام التي هي مضاعفات الأعداد الأولية من القائمة. أولا ، يتم إنشاء قائمة بجميع الأرقام من 2 إلى ن ، ثم تبدأ بالرقم 2 ، ويتم تمييزها على أنها أولية وتتم إزالة جميع الأرقام التي تعد مضاعفاتها من القائمة. ثم ننتقل إلى الرقم التالي غير المسمى ونكرر العملية. كرر هذه العملية حتى تبقى الأعداد الأولية في القائمة فقط. هذه الطريقة أكثر كفاءة من التكرار على المقسومات.
- اختبار ميلر رابين: تعتمد هذه الطريقة على التحقق من رقم للبساطة باستخدام أرقام عشوائية. إنه يعمل على أساس الاحتمال ويسمح لك بتحديد رقم أولي أو رقم يمكن أن يكون مركبا. كلما زاد عدد الشيكات ، كلما كانت النتيجة أكثر دقة.
- اختبار المزرعة: تعتمد هذه الطريقة على نظرية فيرما وتسمح لك بالتحقق بسرعة من الرقم بحثا عن البساطة. ومع ذلك ، فإنه لا يعطي دائما نتائج دقيقة وقد يعطي أعدادا أولية خاطئة.
كل من هذه الأساليب لها مزاياها وعيوبها. يعتمد اختيار الطريقة على المهمة المحددة والدقة المطلوبة للنتائج.
غربال إراتوستينس
غربال إراتوستينس هو خوارزمية للعثور على جميع الأعداد الأولية حتى رقم معين ن. يعتمد على مبدأ الاستبعاد: أولا نفترض أن جميع الأرقام من 2 إلى ن أولية ، ثم نستبعد الأرقام المركبة بالتتابع.
خطوات خوارزمية غربال إراتوستينس:
- قم بإنشاء قائمة بالأرقام من 2 إلى ن.
- حدد الرقم الأول من القائمة وقم بتمييزه على أنه رقم أولي.
- نستبعد من القائمة جميع الأرقام اللاحقة القابلة للقسمة على الرقم الأولي المحدد.
- حدد الرقم التالي غير المسمى في القائمة وكرر الخطوتين 2 و 3.
- كرر الخطوة 4 حتى نتصفح جميع الأرقام الموجودة في القائمة.
في نهاية الخوارزمية ، تكون جميع الأرقام غير المسماة في القائمة أولية.
مزايا غربال إراتوستينس:
- الخوارزمية لها تعقيد خطي ، مما يجعلها سريعة جدا.
- لا يتطلب عمليات حسابية معقدة.
- يتم تنفيذه بسهولة في رمز البرنامج.
عيوب غربال إراتوستينس:
- انها غير فعالة لقيم كبيرة من ن ، لأنه يتطلب كمية كبيرة من الذاكرة.
- إنه غير مناسب للبحث عن الأعداد الأولية في نطاق معين ، ولكن فقط حتى رقم معين ن.
باستخدام غربال إراتوستينس يجعل من الممكن العثور على جميع الأعداد الأولية بكفاءة تصل إلى قيمة معينة من ن. هذه الخوارزمية هي واحدة من أسرع وأسهل الطرق لحل هذه المشكلة.
اختبار ميلر رابين
اختبار ميلر رابين هو خوارزمية احتمالية للتحقق من رقم للبساطة. لأنه يقوم على خصائص الأعداد الأولية ويسمح لك لتحديد مع احتمال كبير ما إذا كان عدد بسيط أو مركب.
خوارزمية ميلر رابين ينفذ عدة تكرارات للتحقق من عدد للبساطة. في كل تكرار ، يتم تحديد قاعدة عشوائية أ ويتم فحص الشرط:
أ^(ن-1 ) mod 1 وزارة الدفاع ن
أين ن هو الرقم المراد التحقق منه. إذا لم يتم استيفاء هذا الشرط ، فإن الرقم مركب تماما. إذا تم استيفاء الشرط ، فمع الاحتمال 1/2 يكون الرقم أوليا ، وتنتقل الخوارزمية إلى التكرار التالي. يتم تنفيذ المزيد من التكرارات ، وارتفاع دقة الاختبار. ولكن بعد عدة تكرارات ، يمكن اعتبار نتيجة الخوارزمية موثوقة بما فيه الكفاية.
اختبار ميلر رابين سريع جدا ، مقارنة مع خوارزميات أخرى للتحقق من الأرقام للبساطة. بالإضافة إلى ذلك ، فإنه ينطبق أيضا على أعداد كبيرة جدا.
خوارزمية ميلر رابين لديها بعض القيود. يعتمد احتمال الخطأ على القاعدة المختارة أ. زيادة عدد التكرارات يعطي دقة أكبر للنتيجة ، ولكن يبطئ الخوارزمية.
يستخدم اختبار ميلر رابين على نطاق واسع عند العمل بأعداد كبيرة ، وخاصة خوارزميات التشفير ، حيث يلزم التحقق السريع من بساطة الأرقام.
اختبار المزرعة
اختبار فيرما هو أحد طرق التحقق من الرقم من أجل البساطة. تعتمد الطريقة على نظرية فيرما الصغيرة ، والتي تنص على أنه إذا كان الرقم أ هو رئيس ولا يقبل القسمة على ص ، ثم أب a أ (وزارة الدفاع ص).
يتكون إجراء اختبار فيرما من اختيار رقم عشوائي أ في النطاق من 2 إلى ن-1 والتحقق من المساواة بين-1 1 1 (وزارة الدفاع ن). إذا كان هناك رقم واحد على الأقل أ لا تحمل هذه المساواة ، فإن الرقم ن مركب تماما. إذا كانت المساواة تنطبق على جميع الأرقام أ ، فمن المحتمل أن يكون الرقم ن أوليا.
ومع ذلك ، تجدر الإشارة إلى أن اختبار فيرما ليس موثوقا به تماما للتحقق من الأرقام من أجل البساطة ، نظرا لوجود أرقام كارمايكل التي يعطي اختبار فيرما نتائج غير صحيحة. لتكون أكثر ثقة في بساطة الرقم ، من الأفضل استخدام خوارزميات أكثر تعقيدا.
سؤال وجواب
كيف يمكنني العثور بسرعة على عدد الأعداد الأولية من 1 إلى ن?
للعثور بسرعة على عدد الأعداد الأولية من 1 إلى ن ، يمكنك استخدام خوارزمية غربال إراتوستينس. انها تسمح لك للعثور على جميع الأعداد الأولية تصل إلى عدد معين ن في س (ن سجل سجل ن) العمليات. من الضروري إنشاء مجموعة من الأرقام من 2 إلى ن وتصفية الأرقام المركبة بالتتابع ، بدءا من أصغر عدد أولي.
كيف تعمل خوارزمية غربال إراتوستينس?
تعمل خوارزمية غربال إراتوستينس على النحو التالي: يتم إنشاء مجموعة من الأرقام من 2 إلى ن. ثم يتم التخلص من الأرقام المركبة بالتتابع ، بدءا من أصغر عدد أولي (2). للقيام بذلك ، يتم فرز جميع الأرقام من 2 إلى الجذر التربيعي(ن) ، وإذا لم يتم وضع علامة على الرقم كمركب ، فإنه يعتبر بسيطا ، ويتم وضع علامة على جميع مضاعفاته كمركب. ثم ننتقل إلى الرقم التالي غير المسمى ونكرر العملية. نتيجة لذلك ، تظل جميع الأرقام غير المميزة أولية ، ويمكن حساب عدد الأعداد الأولية حتى ن من المصفوفة الناتجة.
هل هناك طرق بديلة لحساب الأعداد الأولية?
نعم ، إلى جانب خوارزمية غربال إراتوستينس ، هناك طرق أخرى لحساب الأعداد الأولية. على سبيل المثال ، خوارزميات اختبار البساطة مثل اختبار فيرما أو اختبار ميلر رابين. إنها تسمح لك بالتحقق من الرقم بحثا عن البساطة ، لكن لا تحسب عدد الأعداد الأولية حتى رقم معين ن. هناك أيضا خوارزميات تعتمد على الصيغ الرياضية التي تسمح لك بحساب الأعداد الأولية ، ولكنها قد تكون معقدة وتتطلب موارد حسابية كبيرة.
هل من الممكن استخدام خوارزمية غربال إراتوستينس لأعداد كبيرة?
يمكن استخدام خوارزمية غربال إراتوستينس لحساب الأعداد الأولية حتى أعداد كبيرة جدا. ومع ذلك ، في حالة الأعداد الكبيرة جدا ، قد تكون هناك حاجة إلى قدر كبير من الذاكرة لتخزين مجموعة من الأرقام والأرقام المركبة المسمى. تحتاج أيضا إلى مراعاة وقت تنفيذ الخوارزمية ، والذي يمكن أن يكون مهما. للحصول على عد أكثر كفاءة للأعداد الأولية إلى أعداد كبيرة ، يمكن استخدام إصدارات محسنة من خوارزمية غربال إراتوستينس أو خوارزميات أخرى تعتمد على الصيغ الرياضية.