العدد الأولي هو عدد طبيعي أكبر من واحد ، وله قاسمان فقط: واحد ونفسه. على سبيل المثال ، الأرقام 2 و 3 و 5 و 7 وما إلى ذلك هي أرقام أولية ، لأنها لا تقبل القسمة على أي أرقام أخرى باستثناء نفسها ورقم واحد. على عكس الأعداد الأولية ، تحتوي الأرقام المركبة على أكثر من مقسومين.
هناك عدة طرق للتحقق من عدد للبساطة. واحدة من أبسط الطرق وأكثرها فعالية هي طريقة فرز القواسم. باستخدام هذه الطريقة ، نقسم عددا بالتسلسل على جميع الأعداد الطبيعية ، بدءا من 2 وتنتهي بجذر الرقم. إذا لم نجد أي قواسم ، فإن العدد هو عدد أولي. إذا وجدنا مقسوما واحدا على الأقل ، فسيكون الرقم مركبا.
على سبيل المثال ، للتحقق مما إذا كان الرقم 13 أوليا ، نقسمه على جميع الأرقام حتى جذر 13 (أي 3). في هذه الحالة ، لا نجد أي قواسم ، لذا فإن العدد 13 هو عدد أولي.
هناك طريقة أخرى للتحقق من البساطة في الرقم وهي التحقق من قابلية القسمة على جميع الأعداد الأولية حتى جذرها. إذا كان الرقم قابلا للقسمة على رقم أولي واحد على الأقل ، فهو رقم مركب. إذا كان الرقم غير قابل للقسمة على أي عدد أولي ، فهو أولي.
في هذه المقالة ، نظرنا في طريقتين بسيطتين وفعالتين للتحقق من الرقم من أجل البساطة. إنها تسمح لك بتحديد ما إذا كان الرقم بسيطا أم مركبا بسرعة وبدقة.
- الجزء 1: ما هو عدد أولي?
- التعريف والخصائص الأساسية للأعداد الأولية
- القسم 2: طرق التحقق من الرقم من أجل البساطة
- غربال إراتوستينس
- الباب 3: خوارزمية التحقق من الرقم من أجل البساطة
الجزء 1: ما هو عدد أولي?
تعتبر الأعداد الأولية اللبنات الأساسية للنظام العددي بأكمله. يمكن تمثيل أي عدد صحيح كمنتج للأعداد الأولية ، والمعروفة باسم النظرية الأساسية للحساب. على سبيل المثال ، يمكن تمثيل الرقم 85 كمنتج للأعداد الأولية: 5 * 17. تستخدم الأعداد الأولية أيضا في خوارزميات مختلفة للتحقق من قابلية القسمة والعوامل.
الأعداد الأولية هي 2, 3, 5, 7, 11, 13, 17, 19 الخ . هناك عدد لا حصر له منها ويمكن العثور عليها باستخدام طرق وخوارزميات مختلفة.
يعد العثور على الأعداد الأولية مهمة صعبة ، حيث توجد أعداد غير محدودة ، ويستغرق الأمر وقتا معينا للتحقق من كل رقم. هناك طرق مختلفة لاختبار بساطة الرقم ، مثل اختبار فيرما واختبار ميلر رابين واختبار رابين ميلر.
في المستقبل ، سننظر بمزيد من التفصيل في كيفية التحقق مما إذا كان الرقم أوليا ، وما هي الخوارزميات التي يمكن استخدامها لهذا الغرض.
التعريف والخصائص الأساسية للأعداد الأولية
خصائص الأعداد الأولية:
- العدد الأولي دائما أكبر من 1.
- لا يمكن أن يكون العدد الأولي قوة موجبة للأرقام الأخرى ، باستثناء نفسه. على سبيل المثال ، الرقم 4 ليس أوليا ، لأنه 2 إلى القوة الثانية (2*2).
- مجموعة جميع الأعداد الأولية لانهائية. تم إثبات هذا البيان من قبل عالم الرياضيات اليوناني القديم إقليدس ، ومنذ ذلك الحين تم تأكيده مرارا وتكرارا من قبل العديد من علماء الرياضيات الآخرين.
- يمكن التعبير عن كل عدد طبيعي أكبر من 1 كمنتج للأعداد الأولية وبطريقة فريدة. تعرف هذه الخاصية باسم النظرية الأساسية للحساب وتشكل الأساس الأساسي للعمل مع الأرقام.
- تشكل الأعداد الأولية تسلسلا: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 وهلم جرا. في هذا التسلسل ، يكون كل رقم لاحق أوليا وأكبر من الرقم السابق.
القسم 2: طرق التحقق من الرقم من أجل البساطة
هناك عدة طرق للتحقق من بساطة الأرقام التي يمكن استخدامها في البرمجة:
1. طريقة فرز المقسومات: تتمثل هذه الطريقة في تمرير جميع الأرقام من 2 إلى جذر رقم معين والتحقق من قابلية القسمة لكل رقم من هذه الأرقام. إذا كان الرقم قابلا للقسمة على أي منهم بدون باقي ، فهو ليس أوليا. عند استخدام هذه الطريقة ، من المهم اختيار الطريقة المثلى للتكرار على المقسومات لتقليل تكاليف الوقت.
2. طريقة غربال إراتوستينس: تعتمد هذه الطريقة على مبدأ الاستبعاد. أولا ، يتم إنشاء قائمة بجميع الأعداد الصحيحة من 2 إلى رقم معين. بعد ذلك ، يتم فرز جميع الأرقام التي هي مضاعفات الرقم الحالي واحدا تلو الآخر. بعد الانتهاء من الخوارزمية ، ستبقى الأعداد الأولية فقط. هذه الطريقة فعالة بشكل خاص عند التحقق من الأعداد الكبيرة.
3. الأساليب الاحتمالية: تعتمد الأساليب الاحتمالية على استخدام الأرقام والإحصاءات العشوائية. أنها تسمح لك لتحديد مع احتمال كبير ما إذا كان عدد بسيط أو مركب. واحدة من أكثر الطرق الاحتمالية شيوعا هي طريقة ميلر رابين.
يعتمد استخدام طريقة معينة على سياق ومتطلبات مهمة معينة. من الضروري اختيار الطريقة المناسبة اعتمادا على حجم الرقم والدقة المطلوبة للتحقق.
يعد أمان وكفاءة الخوارزميات للتحقق من الأرقام من أجل البساطة من المهام المهمة في التشفير والمجالات الأخرى التي يتطلب فيها استخدام الأعداد الأولية.
غربال إراتوستينس
- إنشاء قائمة بالأرقام من 2 إلى رقم معين.
- بدءا من الرقم 2 ، نضع علامة على جميع مضاعفاته كأرقام مركبة.
- كرر الخطوة 2 للرقم التالي غير المميز.
- تستمر العملية حتى يتم وضع علامة على جميع الأرقام أو حتى يتم الوصول إلى رقم معين.
نتيجة للخوارزمية ، ستكون جميع الأرقام غير المسماة في القائمة أعدادا أولية.
هذه الطريقة فعالة للبحث عن الأعداد الأولية في نطاق صغير ، حيث أنه من الممكن التخلص من العديد من الأرقام غير البسيطة بخطوة بسيطة.
يمكن استخدام غربال إراتوستينس في البرمجة للتحقق مما إذا كان رقم معين أوليا ، أو للعثور على جميع الأعداد الأولية حتى حد معين.
القسم 3: خوارزمية للتحقق من الرقم من أجل البساطة
- حدد الرقم الذي تريد التحقق من البساطة.
- أولا ، تحقق مما إذا كان الرقم أقل من أو يساوي 1. إذا كان الأمر كذلك ، فإن الرقم ليس أوليا.
- بعد ذلك ، تحقق مما إذا كان الرقم قابلا للقسمة تماما على أي رقم بخلاف 1 وهو نفسه. إذا كان قابلا للقسمة ، فإن الرقم مركب.
- إذا كان الرقم غير قابل للقسمة تماما على أي رقم من 2 إلى الجذر التربيعي لهذا الرقم ، فهو أولي.
قم بتشغيل بعض الأمثلة لفهم الخوارزمية بشكل أفضل:
- دعنا نتحقق من الرقم 7 بحثا عن البساطة:
- الرقم 7 أكبر من 1 ، لذلك نواصل التحقق.
- الرقم 7 غير قابل للقسمة تماما على أي رقم من 2 إلى 6 (الجذر التربيعي لـ 7) ، لذا فهو بسيط.
- دعنا نتحقق من الرقم 12 بحثا عن البساطة:
- الرقم 12 أكبر من 1 ، لذلك نواصل التحقق.
- الرقم 12 قابل للقسمة تماما على 2 ، لذا فهو مركب.
حتى تتمكن من استخدام هذه الخوارزمية للتحقق من الأرقام للبساطة.