التحليل إلى العوامل الأولية والقواسم
تفكيك N إلى قوى أولية وعدّ القواسم
التحليل إلى العوامل الأولية والقواسم درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
فكّك N
كل عدد صحيح أكبر من 1 هو حاصل ضرب وحيد لأعداد أولية. ويؤدي العثور على هذا التفكيك، أي التحليل إلى العوامل الأولية، إلى حل كثير من مسائل نظرية الأعداد. 🧩
فكرة القسمة التجريبية
استخرج أصغر عدد أولي يقسم n، واقسمه منه، ثم كرّر العملية. تعمل هذه القسمة التجريبية البسيطة على تفكيك n حتى يصل إلى 1.
كرّر حتى الجذر
اختبر القواسم i ما دام i*i لا يتجاوز n. وبعد الجذر التربيعي، يمكن أن يبقى عامل أولي واحد فقط على الأكثر.
while i * i <= n:
...استخرج كل عامل
ما دام i يقسم n، واصل القسمة وسجّل i. يلتقط ذلك أس ذلك العدد الأولي بالكامل قبل الانتقال إلى العامل التالي.
while n % i == 0:
factors.append(i)
n //= iالعامل الأولي المتبقي
بعد انتهاء الحلقة، إذا ظلت قيمة n أكبر من 1، فهي نفسها عامل أولي أكبر من الجذر التربيعي. أضفها مرة واحدة.
if n > 1:
factors.append(n)الإجراء الكامل
تمنحك هذه الخطوات معًا تحليلًا إلى عوامل في زمن O(sqrt n)، مع إرجاع كل عدد أولي بتعدده الكامل وبالترتيب.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fجمّعها في أسس
عند عدّ القواسم، تريد كل عدد أولي مع أسّه، مثل 2^3 بدلًا من 2,2,2. ويحصي Counter التكرارات بوضوح.
from collections import Counter
exp = Counter(factorize(n))صيغة القواسم
إذا كان n يساوي p1^a مضروبًا في p2^b، فإن عدد القواسم يساوي (a+1) مضروبًا في (b+1). إذ يضيف كل أس خيارًا واحدًا إضافيًا.
عدّ القواسم
اضرب واحدًا مضافًا إلى كل أسّ من أسس الأعداد الأولية. يمنحك ذلك عدد القواسم الكلي من دون سردها واحدًا واحدًا.
count = 1
for e in exp.values():
count *= (e + 1)مجموع القواسم
تجمع صيغة مرتبطة القواسم باستخدام المتسلسلة الهندسية لكل عدد أولي. يساعدك فهمها في حل مسائل الأعداد الكاملة ومسائل aliquot.
تسريع باستخدام غربال
عند إجراء العديد من عمليات التحليل إلى عوامل، احسب مسبقًا أصغر عامل أولي لكل عدد باستخدام غربال. بعد ذلك يحلل كل استعلام العدد إلى عوامله في log n خطوة.
تحقق سريع
طبّق صيغة عدّ القواسم على عدد محدد.
مراجعة
يمكنك الآن تحليل N إلى عوامله بالقسمة التجريبية في O(sqrt n)، والتقاط العامل الأولي المتبقي، وتجميع الأسس، وعدّ القواسم باستخدام صيغة الضرب. ✅
الأسئلة الشائعة
هل درس «التحليل إلى العوامل الأولية والقواسم» مجاني؟
نعم — نص درس «التحليل إلى العوامل الأولية والقواسم» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «التحليل إلى العوامل الأولية والقواسم»؟
تفكيك N إلى قوى أولية وعدّ القواسم تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «التحليل إلى العوامل الأولية والقواسم»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- GCD وLCM والخوارزمية الإقليدية
- اختبار الأولية حتى sqrt(n)
- غربال إراتوستينس
- التحليل إلى العوامل الأولية والقواسم