يعد التحقق من رقم للبساطة أحد أكثر المهام شيوعا في البرمجة. يمكن استخدام خوارزميات مختلفة للتحقق من الأعداد الأولية ، لكن بايثون لديها طريقة بسيطة وفعالة.
الأعداد الأولية هي أساس العديد من خوارزميات التشفير ، لذا فإن التحقق منها له أهمية عملية كبيرة. ومع ذلك ، في معظم الحالات ، يعد التحقق من الرقم الأولي مهمة تعليمية تساعدك على فهم أساسيات البرمجة.
في بيثون ، يمكنك استخدام وظيفة إيسبريم () من مكتبة الرياضيات للتحقق من عدد للبساطة. ترجع الدالة صحيح إذا كان الرقم هو رئيس الوزراء ، وخطأ خلاف ذلك. هذه الطريقة بسيطة للغاية وتسمح لك بالتحقق من بساطة الرقم دون كتابة خوارزميات معقدة.
- كيفية التحقق من عدد أولي في بايثون: طريقة سهلة
- ما هو العدد الأولي ولماذا من المهم التحقق منه
- الطريقة 1: التكرار من خلال القواسم إلى جذر الرقم
- الطريقة 2: استخدام خوارزمية إراتوستينس
- الطريقة 3: حساب ما يصل إلى نصف الرقم
- الطريقة 4: التحقق من القواسم الفردية فقط
- مثال على الكود: التحقق من رقم أولي في بايثون
- موجز: اختر الطريقة الأكثر فعالية للتحقق من عدد أولي في بايثون
- سؤال وجواب
- كيف يمكنني التحقق مما إذا كان الرقم هو رئيس باستخدام بيثون?
- ما خوارزمية يمكن استخدامها للتحقق الأعداد الأولية في بيثون?
- هل بيثون لديها وظيفة مدمجة لفحص الأعداد الأولية?
- والتحقق من عدد أولي في بيثون مهمة صعبة للمبتدئين?
- هل من الممكن استخدام الاختيار عدد أولي في بيثون لتحسين خوارزميات أخرى?
كيفية التحقق من عدد أولي في بايثون: طريقة سهلة
الأعداد الأولية هي أرقام لها مقسومان فقط: واحد والرقم نفسه. في البرمجة ، غالبا ما تكون هناك حاجة للتحقق مما إذا كان رقم معين أوليا. بيثون لديه طريقة بسيطة للتحقق من عدد للبساطة.
للتحقق من عدد أولي في بايثون ، يمكنك استخدام الخوارزمية التالية:
- الرقم الذي تم إدخاله ن يتم التحقق من قابلية القسمة على الأرقام من 2 إلى ن-1.
- إذا كان الرقم ن يقبل القسمة على رقم واحد على الأقل ، فإن الرقم ن ليس أوليا.
- إذا كان الرقم ن لا يقبل القسمة على أي من الأرقام من 2 إلى ن-1 ، ثم الرقم ن هو رئيس الوزراء.
دعونا تحديد وظيفة من شأنها أن تأخذ عددا كوسيطة وإرجاع نتيجة الاختيار البساطة:
| كود: |
|---|
| (ن): |
| لأني في النطاق (2 ، ن): |
| إذا ن ٪ أنا = = 0: |
| العودة كاذبة |
| العودة الحقيقية |
الآن يمكنك استدعاء وظيفة عن طريق تمرير ذلك الرقم الذي يحتاج إلى التحقق من البساطة:
| كود: |
|---|
| عدد = كثافة العمليات (الإدخال ("أدخل رقم:")) |
| إذا كان _رئيس الوزراء (عدد): |
| طباعة ("رقم" ، رقم ، "بسيط") |
| آخر: |
| طباعة ("رقم" ، رقم، "ليست بسيطة") |
على سبيل المثال ، إذا تم إدخال الرقم 7 ، فسيخرج البرنامج "الرقم 7 أولي".
وهكذا ، وذلك باستخدام وظيفة بسيطة يسمح لك بسرعة وسهولة التحقق من الأرقام للبساطة في بيثون.
ما هو العدد الأولي ولماذا من المهم التحقق منه
الأعداد الأولية هي أعداد طبيعية أكبر من واحد ، والتي لا تقبل القسمة إلا على نفسها وعلى واحد بدون الباقي.
الأعداد الأولية مهمة في الرياضيات والتشفير. إنها اللبنات الأساسية للأرقام الأخرى ويمكن استخدامها لتشفير البيانات وحمايتها. على سبيل المثال ، يتم استخدامها على نطاق واسع في خوارزميات التشفير رسا.
يلعب التحقق من رقم للبساطة دورا مهما في تطوير الخوارزميات والبرامج المتعلقة بالعمل مع الأرقام. يتيح لك الشيك تحديد ما إذا كان الرقم بسيطا أم مركبا. إذا كان الرقم أوليا ، فيمكنك استخدام خوارزميات محسنة تعمل فقط مع الأعداد الأولية وتعمل بشكل أسرع.
يمكن أن يكون التحقق من الرقم بحثا عن البساطة مفيدا في العديد من المهام ، بما في ذلك إيجاد العوامل الأولية وتحديد القاسم المشترك الأكبر لرقمين. هذا يساعد على تحسين تشغيل البرنامج وتقليل التعقيد الحسابي.
إحدى الطرق الشائعة للتحقق من الرقم من أجل البساطة هي طريقة التكرار على المقسومات. تشمل الطرق الأخرى استخدام صيغة فيرما واختبار ميلر رابين وخوارزميات أخرى.
من المهم أن تكون قادرا على التحقق من الأرقام بحثا عن البساطة واستخدام الخوارزميات المحسنة للعمل مع الأعداد الأولية من أجل زيادة كفاءة البرنامج وضمان أمان البيانات.
الطريقة 1: التكرار من خلال القواسم إلى جذر الرقم
واحدة من أبسط الطرق وأكثرها فعالية للتحقق مما إذا كان الرقم أوليا هي التكرار من خلال جميع قواسم الرقم حتى جذره التربيعي.
بالنسبة لهذه الخوارزمية ، سنقوم بتقسيم رقم بالتتابع على جميع القواسم الممكنة ، بدءا من 2 وتنتهي بجذرها التربيعي. إذا كان الرقم قابلا للقسمة على أي من هذه القواسم بدون الباقي ، فهو ليس عددا أوليا.
سيتم التحقق من بساطة الرقم باستخدام الخطوات التالية:
- يتم إدخال رقم يحتاج إلى التحقق من البساطة.
- أوجد الجذر التربيعي لهذا الرقم وقم بتقريبه إلى أقرب عدد صحيح أكبر.
- كرر بشكل متكرر من خلال جميع الأرقام من 2 إلى الجذر المستدير.
- إذا كان الرقم قابلا للقسمة على أي من هذه الأرقام بدون باقي ، فهو ليس أوليا. خلاف ذلك ، الأمر بسيط.
يوضح الرمز أدناه تنفيذ هذه الخوارزمية في بايثون:
استيراد الرياضيات
(ن):
إذا ن < = 1:
العودة كاذبة
الرياضيات.إسقرت (ن)
لأني في النطاق (2 ، الجذر التربيعي + 1):
إذا ن ٪ أنا = = 0:
العودة كاذبة
العودة الحقيقية
الرقم = كثافة العمليات (الإدخال ("أدخل رقما للتحقق من البساطة:"))
إذا كان _رئيس الوزراء (عدد):
طباعة (و " {رقم} هو عدد أولي.")
آخر:
طباعة (و " {عدد} ليس رئيس الوزراء
. بعد ذلك ، باستخدام حلقة ، يتم فرز جميع الأرقام من 2 إلى الجذر المستدير الشامل ، وإذا تم تقسيم الرقم على أي من هذه الأرقام بدون باقي ، فهو ليس أوليا. خلاف ذلك ، يتم إرجاع القيمة الحقيقية ، ويعتبر الرقم أوليا.
الطريقة 2: استخدام خوارزمية إراتوستينس
خوارزمية إراتوستينس هي طريقة فعالة للعثور على جميع الأعداد الأولية في نطاق معين. يعتمد على مبدأ استبعاد الأرقام غير الأولية.
خطوات خوارزمية إراتوستينس:
- قم بإنشاء قائمة بالأرقام من 2 إلى ن ، أين ن هو الرقم الذي تريد العثور عليه الأعداد الأولية.
- اضبط القيمة الأولية لـ ص إلى 2 ، أصغر عدد أولي.
- ضع علامة على جميع الأرقام في القائمة التي تعد مضاعفات ص كمركب (ليس بسيطا). أي إذا كان الرقم قابلا للقسمة على ص بدون الباقي ، فهو ليس أوليا.
- ابحث عن الرقم التالي غير المسمى في القائمة ، أكبر من ص ، واضبطه على ص ، ثم ارجع إلى الخطوة 3.
- كرر الخطوات من 3 إلى 4 حتى تصل إلى رقم يمثل مربع ن.ستكون جميع الأرقام المتبقية غير المسماة في القائمة بسيطة.
مثال على استخدام خوارزمية إراتوستينس:
(ن):
الأعداد الأولية = [صحيح] * (ن + 1)
ع = 2
بينما ص * ص < = ن:
إذا يعبي [ع]:
لأني في النطاق (ص * ص ، ن + 1 ، ص):
الأعداد الأولية [أنا] = خطأ
ف + = 1
العودة [س ل س في نطاق (2 ، ن + 1) إذا يعبي [س]]
ن = 20
الأعداد الأولية = غربلة _ من _ راتوستينس (ن)
طباعة (الأعداد الأولية)
في هذا المثال ، تأخذ الوظيفة "غربلة _ من _ راتوستينس" المعلمة ن ، الذي يحدد النطاق الذي تريد العثور فيه على الأعداد الأولية. تقوم الخوارزمية بإرجاع قائمة بجميع الأعداد الأولية في هذا النطاق.
سيؤدي استدعاء الوظيفة "غربلة من _ راتوستينس (20)" إلى إرجاع قائمة [2, 3, 5, 7, 11, 13, 17, 19], لأن هذه كلها أعداد أولية في النطاق من 2 إلى 20.
خوارزمية إراتوستينس هو أكثر كفاءة من التحقق من كل رقم للبساطة ، وخاصة بالنسبة لنطاقات كبيرة من الأرقام.
الطريقة 3: حساب ما يصل إلى نصف الرقم
هناك طريقة أخرى بسيطة وفعالة للتحقق من بساطة الرقم وهي التحقق من المقسومات حتى نصف الرقم فقط. هذا يوفر قدرا كبيرا من موارد الحوسبة ، خاصة بالنسبة للأعداد الكبيرة.
الخوارزمية هي كما يلي:
- نتحقق من الحالة عندما يكون الرقم أقل من أو يساوي 1. في هذه الحالة ، الرقم ليس أوليا.
- نتحقق من الحالة عندما يكون الرقم 2. في هذه الحالة ، يكون الرقم أوليا.
- نتحقق مما إذا كان الرقم قابلا للقسمة تماما على أي رقم من 2 إلى نصف الرقم. إذا كان قابلا للقسمة ، فإن الرقم ليس أوليا.
- إذا لم يتم استيفاء أي من الشروط السابقة ، فسيكون الرقم أوليا.
يوجد أدناه مثال على كود بايثون الذي ينفذ هذه الطريقة للتحقق من رقم أولي إلى نصف رقم:
(ن):
إذا ن < = 1:
العودة كاذبة
إذا ن = = 2:
العودة الحقيقية
لأني في النطاق (2 ، ن // 2 + 1):
إذا ن ٪ أنا = = 0:
العودة كاذبة
العودة الحقيقية
في هذا الرمز ، المتغير " ن " هو رقم نتحقق من بساطته. ترجع الدالة صحيح إذا " ن " هو عدد أولي ، وخطأ خلاف ذلك.
هذه الطريقة هي واحدة من أبسط وأسرع الطرق للتحقق من عدد للبساطة. إنها مناسبة للأعداد الكبيرة ويمكن استخدامها في العديد من التطبيقات التي تتطلب التحقق من الأرقام من أجل البساطة.
الطريقة 4: التحقق من القواسم الفردية فقط
طريقة التحقق من عدد أولي على أساس التحقق من القواسم الفردية فقط هي طريقة أخرى بسيطة وفعالة لتحديد عدد أولي في بايثون.
بادئ ذي بدء ، دعونا نتذكر أن الأعداد الأولية هي أعداد طبيعية ، أعداد كبيرة لها قاسمان فقط — واحد وهذا الرقم نفسه. ومع ذلك ، باستثناء الرقم 2 ، فإن جميع الأعداد الأولية غريبة.
باستخدام هذه الحقيقة ، يمكننا تسريع عملية التحقق من بساطة الرقم بشكل كبير. يكفي التحقق فقط من القواسم الفردية لعدد يصل إلى جذره التربيعي.
للتحقق مما إذا كان الرقم س هو رئيس الوزراء ، وهو ما يكفي لتكرار على جميع الأرقام الفردية أنا من 3 إلى الجذر التربيعي(س) ، وتحقق ما إذا كان س هو القسمة على أنا دون بقية. إذا كان قابلا للقسمة ، فإن س ليس عددا أوليا ويمكننا إكمال الشيك.
إذا لم يكن أي من الأرقام الفردية مقسوما على س ، فإن س هو رقم أولي.
هنا هو تنفيذ بيثون بسيط من هذه الطريقة:
استيراد الرياضيات
(ن):
إذا ن< = 1:
العودة كاذبة
إذا ن= = 2:
العودة الحقيقية
إذا ن % 2 = = 0:
العودة كاذبة
الحد الأقصى = الرياضيات.إسقرت (ن) + 1
بالنسبة لي في النطاق (3 ، الحد الأقصى للقسم ، 2):
إذا ن ٪ أنا = = 0:
العودة كاذبة
العودة الحقيقية
هذه الطريقة بسيطة وسريعة وسهلة الفهم. يمكن استخدامه لاختبار بساطة الأرقام من أي حجم.
ومع ذلك ، إذا كنت بحاجة إلى اختبار مجموعة من الأرقام للبساطة ، ثم غربال إراتوستينس أو اختبار ميلر رابين قد تكون خوارزميات أكثر فعالية.
مثال على الكود: التحقق من رقم أولي في بايثون
فيما يلي مثال على رمز بايثون الذي يسمح لك بالتحقق مما إذا كان الرقم أوليا:
(ن):
إذا ن < 2:
العودة كاذبة
لأني في النطاق (2 ، كثافة العمليات(ن * * 0.5) + 1):
إذا ن ٪ أنا = = 0:
العودة كاذبة
العودة الحقيقية
العدد = 17
إذا كان _رئيس الوزراء (عدد):
طباعة (و "{رقم} هو عدد أولي")
آخر:
طباعة (و "{رقم} ليس عددا أوليا")
في هذا المثال ، تأخذ دالة إيس_بريم () الرقم ن كوسيطة وتتحقق مما إذا كانت أولية. ترجع الدالة صحيحا إذا كان الرقم أوليا ، وخطأ إذا لم يكن الرقم أوليا.
للتحقق من قواسم الرقم ن ، أ للحلقة يستخدم ، والذي يمتد من 2 إلى كثافة العمليات(ن ** 0.5) + 1. لاحظ أننا نتحقق من القواسم فقط حتى الجذر التربيعي للرقم ن ، حيث يتم تكرارها بترتيب عكسي.
في المثال أعلاه ، يتم التحقق من بساطة الرقم 17 ، وإذا كان بسيطا ، يتم عرض الرسالة "17 هو رقم أولي". خلاف ذلك ، يتم عرض الرسالة "17 ليس رقما أوليا".
ملخص: اختر الطريقة الأكثر فعالية للتحقق من عدد أولي في بايثون
في بايثون ، هناك عدة طرق للتحقق مما إذا كان الرقم أوليا أم لا. عندما يتعلق الأمر باختيار الطريقة الأكثر فعالية ، فإن ذلك يعتمد على عدة عوامل ، مثل حجم الرقم والدقة المطلوبة.
واحدة من أبسط الطرق وأكثرها شيوعا للتحقق من الأعداد الأولية هي طريقة فرز المقسومات. وهو يتألف من المرور بجميع الأرقام من 2 إلى ن - 1 والتحقق مما إذا كان الرقم قابلا للقسمة على هذه الأرقام بدون الباقي. إذا كان رقم واحد على الأقل من 2 إلى ن-1 يقسم الرقم بدون الباقي ، فهو ليس أوليا. ومع ذلك ، فإن هذه الطريقة ليست الأكثر فاعلية عند العمل بأعداد كبيرة ، لأنها تتطلب التكرار على مجموعة من المقسومات.
طريقة أكثر فعالية لفحص الأعداد الأولية هي طريقة "نظرية فيرما الصغيرة". على النحو التالي: لعدد معين ن ، يتم تحديد رقم عشوائي أ من 2 إلى ن-1 ، ويتم حساب^(ن-1) وزارة الدفاع ن. إذا كانت النتيجة لا تساوي 1 ، فإن الرقم ن ليس رئيس الوزراء. ومع ذلك ، فإن هذه الطريقة ليست موثوقة تماما وقد تعطي نتائج خاطئة لبعض الأرقام.
طريقة أخرى فعالة لفحص الأعداد الأولية هي طريقة "اختبار ميلر رابين". كما أنه يستخدم أرقاما عشوائية للتحقق مما إذا كان الرقم أوليا. الطريقة هي كما يلي: لعدد معين ن ، يتم تحديد رقم عشوائي أ من 2 إلى ن-1 ، ويتم التحقق مما إذا كان ^ (ن-1) وزارة الدفاع ن يساوي 1. إن لم يكن ، ثم عدد ن ليس رئيس الوزراء. هذه الطريقة أكثر موثوقية من طريقة فرز القواسم وطريقة نظرية فيرما الصغيرة.
ومع ذلك ، عند العمل بأعداد كبيرة جدا ، قد يكون من الضروري استخدام طرق أكثر تعقيدا مثل اختبار لوكاس لومير أو اختبار سولوفي ستراسين للتحقق من بساطتها. تعمل هذه الأساليب على أساس الخوارزميات الخاصة والإنشاءات الرياضية ، وهي مصممة للعمل مع أعداد المئات والآلاف من الشخصيات.
| الطريقة | الفعالية | الحواشي |
|---|---|---|
| القوة الغاشمة من القواسم | منخفض | مناسبة للأعداد الصغيرة |
| نظرية فيرما الصغيرة | المتوسط | قد يعطي نتائج خاطئة |
| اختبار ميلر رابين | عالية | أكثر موثوقية للأعداد الكبيرة |
| اختبار لوكاس لومير | عالية جدا | مصممة للعمل مع أعداد كبيرة |
| اختبار العندليب-ستراسن | عالية جدا | مصممة للعمل مع أعداد كبيرة |
اعتمادا على متطلبات وقيود مهمتك ، يمكنك اختيار الطريقة الأنسب للتحقق من عدد أولي في بايثون.
سؤال وجواب
كيف يمكنني التحقق مما إذا كان الرقم هو رئيس باستخدام بيثون?
خوارزميات مختلفة يمكن استخدامها في بيثون لاختبار عدد للبساطة. واحدة من أسهل الطرق هي التحقق من قواسم الرقم. إذا كان الرقم قابلا للقسمة على 1 ونفسه فقط ، فهو أولي.
ما خوارزمية يمكن استخدامها للتحقق الأعداد الأولية في بيثون?
واحدة من أكثر الخوارزميات فعالية للتحقق من بساطة الرقم هي خوارزمية ميلر رابين. لأنه يقوم على خصائص الأعداد الأولية ويسمح لك لتحديد مع احتمال كبير ما إذا كان عدد بسيط أو مركب.
هل بيثون لديها وظيفة مدمجة لفحص الأعداد الأولية?
لا تحتوي بايثون على وظيفة مضمنة لفحص الأعداد الأولية ، ولكن يمكنك بسهولة كتابة وظيفتك باستخدام إحدى الخوارزميات المتوفرة باللغة ، أو العثور على وحدة أو حزمة جاهزة للتحقق من بساطة الأرقام على الإنترنت.
والتحقق من عدد أولي في بيثون مهمة صعبة للمبتدئين?
قد يكون التحقق من رقم أولي في بايثون مهمة صعبة للمبتدئين ، خاصة إذا كنت تستخدم خوارزميات أكثر تعقيدا مثل خوارزمية ميلر رابين. ومع ذلك ، إذا كنت ترغب في تنفيذ فحص بسيط من المقسومات من عدد ، ثم يمكن أن تكون بسيطة نسبيا.
هل من الممكن استخدام عدد أولي التدقيق في بيثون لتحسين خوارزميات أخرى?
نعم ، يمكن أن يكون التحقق من الرقم الأولي مفيدا لتحسين الخوارزميات الأخرى. على سبيل المثال ، في التشفير ، غالبا ما تستخدم الأعداد الأولية لإنشاء المفاتيح. إذا كان بإمكانك التحقق بشكل فعال مما إذا كان الرقم أوليا ، فيمكنك توفير الوقت والموارد المستخدمة لإنشاء المفاتيح. بالإضافة إلى ذلك ، يمكن أن يكون التحقق من الرقم الأولي مفيدا في تحديد العوامل الأولية للأرقام وإجراء العمليات الحسابية الأخرى.