مشروع Euler project: المشكلة رقم 3

المشكلة رقم 3:
العوامل الرئيسية (prime factors) للعدد 13195 هي 5، 7، 13 و 29.

المطلوب:
ما هو أعلى عامل رئيسي للعدد 600851475143 ؟

الحل:

nbr = 600851475143
i = 1
factor = 0

while i + 1 <= nbr :
   
    i = i + 1
   
    if nbr % i == 0:
        factor = i
        nbr = nbr // i


print  factor

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

الطرقة التي إتبعتها هي كالتالي:

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

شرح الشفرة المصدرية (كود):
1. نستخدم ثلاثة متغيرات: nbr لتعبر عن العدد المعطى لنا في البداية، i التي سنستخدمها كقاسم، ثم factor التي ستحتوي على أعلى عامل رئيسي.
2. نستخدم الحلقة الشرطية while لاستنزاف كل الأرقام و العوامل الرئيسية.
3. i = i+1 فكل دورة من دورات الحلقة تتزايد قيمة المتغيرة i بـ 1
4. إدا كانت قيمة i كقاسم طبيعي لقيمة المتغيرة nbr يتم حفض العامل الرئيسي الذي عثرنا عليه و المعبر عليه بقيمة i حاليا في المتغيرة factor، و من ثم إستخدام الخارج  كالعدد الجديد بحيث نقوم بإسناده إلى المتغيرة nbr
5. في النهاية يتم عرض آخر (أعلى) عامل رئيسي توصلنا إليه و المعبر عنه من خلال المتغيرة factor

التسلسل الذي اتبعته الحلقة هو كالتالي:

i= 71     nbr= 8462696833
i= 839   nbr= 10086647
i= 1471 nbr= 6857
i= 6857 nbr= 1