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

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

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

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

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

1. طرق التحقق من الأرقام من أجل البساطة
2. طريقة فرز المقسومات
3. طريقة التحقق من القابلية للقسمة
4. طرق التحقق على أساس
5. خوارزميات للتحقق من الأرقام من أجل البساطة
6. سؤال وجواب
7. ما هي الطرق التي يمكن استخدامها للتحقق من الأرقام من أجل البساطة?
8. هل من الممكن التحقق بسرعة من عدد كبير للبساطة?
9. ما هو غربال إراتوستينس وكيف يعمل?
10. ما هي الطريقة الأكثر دقة للتحقق من الأرقام من أجل البساطة?

طرق التحقق من الأرقام من أجل البساطة

العدد الأولي هو عدد طبيعي أكبر من عدد لا يحتوي على قواسم أخرى باستثناء واحد وهو نفسه. يعد التحقق من الأرقام بحثا عن البساطة مهمة مهمة في الرياضيات وعلوم الكمبيوتر.

1. طريقة البحث الكامل

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

2. طريقة تقسيم المحاكمة

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

3. طريقة نظرية فيرما الصغيرة

نظرية فيرما الصغيرة هي نظرية تسمح لك بالتحقق من الأرقام من أجل البساطة بشكل أكثر كفاءة. تدعي أنه لأي عدد أولي ص وعدد أولي متبادل أ ، أ^(ص-1) - 1 يقبل القسمة على ص. إذا كانت جميع الأرقام من 2 إلى الجذر التربيعي (ن) ليست قواسم للرقم الذي يتم التحقق منه ، فيمكن اعتبار هذا الرقم أوليا بواسطة نظرية فيرما الصغيرة.

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

عند اختيار طريقة للتحقق من الأرقام من أجل البساطة ، من الضروري مراعاة متطلبات الأداء ودقة النتيجة.

طريقة فرز المقسومات

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

للتحقق من بساطة الرقم عن طريق التكرار من خلال المقسومات ، اتبع الخطوات التالية:

1. حدد الرقم للتحقق.
2. كرر على القواسم المحتملة لرقم من 2 إلى جذر رقم معين.
3. تحقق من كل مقسوم عليه لإمكانية قسمة رقم معين بالكامل.
4. إذا تم العثور على قاسم غير 1 والرقم نفسه ، فإن الرقم مركب ؛ خلاف ذلك ، يعتبر الرقم أوليا.

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

مثال على أداء طريقة فرز المقسومات للرقم 17:

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

طريقة التحقق من القابلية للقسمة

واحدة من أبسط الطرق لتحديد بساطة الرقم هي طريقة التحقق من القابلية للقسمة. جوهر الطريقة هو التحقق مما إذا كان الرقم قابلا للقسمة تماما على أي رقم آخر باستثناء 1 ونفسه.

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

مثال: دعنا نتحقق من الرقم 17 بحثا عن البساطة.

كما يتضح من المثال ، فإن الرقم 17 لا يقبل القسمة تماما على أي رقم باستثناء 1 وهو نفسه ، وبالتالي فهو بسيط.

طريقة التحقق من القابلية للقسمة هي واحدة من أبسط الطرق ، ولكنها ليست الأكثر فعالية للأعداد الكبيرة. تستخدم خوارزميات مختلفة ، مثل خوارزميات إراتوستينس وميلر رابين ، للتحقق من البساطة بشكل أكثر فعالية. تسمح لك هذه الخوارزميات بالتحقق من الأرقام بحثا عن البساطة في عمليات أقل بكثير.

طرق التحقق على أساس

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

يتضمن تطبيق طرق التحقق من صحة الأسباب الخطوات التالية:

1. يتم تحديد القاعدة ب ، والتي سيتم فحصها في النطاق من 2 إلى الجذر التربيعي(ن).
2. يتم حساب ما تبقى من قسمة الرقم ن على الأساس ب.
3. إذا كان الباقي صفرا ، فإن الرقم ن مركب ، لأنه مقسوم على القاعدة ب.
4. إذا لم يكن الباقي صفرا ، فسيتم تحديد القاعدة التالية من النطاق والمتابعة إلى الخطوة 2.
5. إذا تم اختبار جميع القواعد في النطاق دون الحصول على ما تبقى من الصفر ، فإن الرقم ن هو رئيس الوزراء.

هنا مثال على التحقق من الرقم 17 على أساس:

كما يتضح من المثال ، بالنسبة للقواعد من 2 إلى الجذر التربيعي(17) ، لم يتم الحصول على الباقي إلى الصفر ، وبالتالي فإن الرقم 17 هو عدد أولي.

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

خوارزميات للتحقق من الأرقام من أجل البساطة

العدد الأولي هو عدد طبيعي أكبر من عدد يحتوي على قاسمين فقط — 1 وهو نفسه. يعد التحقق من الأرقام بحثا عن البساطة مهمة مهمة في الرياضيات والتشفير.

هناك العديد من الخوارزميات التي تسمح لك بتحديد ما إذا كان الرقم بسيطا أم مركبا.

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

2. اختبار المزرعة: يعتمد هذا الاختبار على نظرية فيرما الصغيرة ، والتي تنص على أنه إذا ص هو عدد أولي و أ هو أي عدد صحيح ليس من مضاعفات ص ، ثم أ إلى القوة (ص—1) مودولو ص سوف يساوي 1. لاختبار عدد ن للبساطة, أرقام عشوائية ويتم تحديد ويتم فحص هذا الشرط. إذا كان الشرط ينطبق على جميع الأرقام العشوائية ، فإن الرقم ن من المحتمل أن يكون أوليا.

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

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

سؤال وجواب

ما هي الطرق التي يمكن استخدامها للتحقق من الأرقام من أجل البساطة?

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

هل من الممكن التحقق بسرعة من عدد كبير للبساطة?

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

ما هو غربال إراتوستينس وكيف يعمل?

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

ما هي الطريقة الأكثر دقة للتحقق من الأرقام من أجل البساطة?

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