كيفية التحقق مما إذا كان الرقم أوليًا في Python

سيعلمك هذا البرنامج التعليمي كيفية كتابة برنامج Python للتحقق مما إذا كان الرقم أوليًا أم لا.

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

في هذا البرنامج التعليمي ، سوف:

  • مراجعة أساسيات الأعداد الأولية ،
  • اكتب كود Python للتحقق مما إذا كان الرقم أوليًا ، و
  • قم بتحسينه بشكل أكبر للحصول على خوارزمية وقت تشغيل O (√n).

لكل هذا وأكثر ، لنبدأ.

ما هو الرقم الأولي؟

لنبدأ بمراجعة أساسيات الأعداد الأولية.

في نظرية الأعداد ، يُقال أن العدد الطبيعي n هو رئيس إذا كان يحتوي على عاملين بالضبط: 1 والرقم نفسه (n). استرجع من الرياضيات في مدرستك: يُقال أن الرقم الأول هو أحد عوامل الرقم n ، إذا قسمت n بالتساوي. ✅

يسرد الجدول التالي بعض الأرقام ، وكل عواملها ، وما إذا كانت أولية.

هل العوامل الرئيسية؟ 11 رقم 21 ، 2 نعم 31 ، 3 نعم 41 ، 2 ، 4 رقم 71 ، 7 نعم ، 151 ، 3 ، 5 ، 15 لا

من الجدول أعلاه يمكننا تدوين الآتي:

  • 2 هو أصغر عدد أولي.
  • 1 هو عامل لكل رقم.
  • كل عدد ن عامل في حد ذاته.

إذن 1 و n عاملان تافهيان لأي عدد n. ولا ينبغي أن يحتوي العدد الأولي على أي عوامل غير هذين.

هذا يعني أنه عندما تنتقل من 2 إلى n – 1 ، يجب ألا تكون قادرًا على إيجاد عامل غير تافه يقسم n بدون باقي.

O (n) خوارزمية للتحقق مما إذا كان الرقم أوليًا في Python

في هذا القسم ، دعونا نجعل النهج أعلاه رسميًا في دالة بايثون.

يمكنك إجراء حلقة عبر جميع الأرقام من 2 إلى n – 1 باستخدام الكائن range () في Python.

في Python ، يعرض النطاق (البدء ، والتوقف ، والخطوة) كائن نطاق. يمكنك بعد ذلك التكرار فوق كائن النطاق للحصول على تسلسل من البداية حتى النهاية حتى التوقف -1 في خطوات الخطوة.

نظرًا لأننا نحتاج إلى مجموعة الأعداد الصحيحة من 2 إلى n-1 ، فيمكننا تحديد النطاق (2، n) واستخدامه جنبًا إلى جنب مع حلقة for.

  تحكم في عتامة النوافذ وحجمها باستخدام عجلة الماوس

إليك ما نود أن نفعله:

  • إذا وجدت رقمًا يقسم n بالتساوي بدون باقي ، يمكنك أن تستنتج فورًا أن الرقم ليس أوليًا.
  • إذا قمت بالحلقة خلال النطاق الكامل للأعداد من 2 وصولًا إلى n – 1 دون العثور على رقم يقسم n بشكل متساوٍ ، فإن الرقم يكون أوليًا.

وظيفة Python للتحقق من الرقم الأولي

باستخدام ما سبق ، يمكننا المضي قدمًا وتحديد الوظيفة is_prime () على النحو التالي.

def is_prime(n):
  for i in range(2,n):
    if (n%i) == 0:
      return False
  return True

دعنا الآن نحلل تعريف الوظيفة أعلاه.

  • الدالة السابقة is_prime () تأخذ عددًا صحيحًا موجبًا n كوسيطة.
  • إذا وجدت عاملاً في النطاق المحدد لـ (2 ، n-1) ، ترجع الدالة False – لأن الرقم ليس أوليًا.
  • ويعيد True إذا اجتزت الحلقة بأكملها دون إيجاد عامل.

بعد ذلك ، دعنا نستدعي الدالة بالوسيطات ونتحقق مما إذا كان الناتج صحيحًا.

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

في الإخراج أعلاه ، ترى أن 2 و 11 عدد أولي (ترجع الدالة True). و 8 و 9 ليسا أوليين (تقوم الدالة بإرجاع خطأ).

كيفية تحسين وظيفة بايثون is_prime ()

يمكننا القيام بتحسين صغير هنا. لاحظ قائمة العوامل في الجدول أدناه.

عدد العوامل 61، 2، 3، 6101، 2، 5، 10181، 2، 3، 6، 9، 18

حسنًا ، يمكننا أن نرى أن العامل الوحيد لـ n الأكبر من n / 2 هو n نفسه.

هذا يعني أنك لست مضطرًا إلى التكرار حتى n – 1. يمكنك بدلاً من ذلك تشغيل الحلقة حتى n / 2 فقط.

إذا لم تجد عاملًا غير تافه حتى n / 2 ، فلن تتمكن من العثور على واحد بعد n / 2 أيضًا.

الآن دعنا نعدل الدالة is_prime () للتحقق من العوامل في النطاق (2، n / 2)

def is_prime(n):
  for i in range(2,int(n/2)):
    if (n%i) == 0:
      return False
  return True

دعنا نمضي قدمًا ونتحقق من الإخراج من خلال بعض استدعاءات الوظائف.

is_prime(9)
# False

is_prime(11)
# True

على الرغم من أنه قد يبدو أننا قمنا بالتحسين ، إلا أن هذه الخوارزمية ليست أكثر كفاءة من سابقتها من حيث تعقيد وقت التشغيل. في الواقع ، كلاهما لهما تعقيد وقت تشغيل O (n): يتناسب مع قيمة n أو خطي في n.

هل يمكننا أن نفعل ما هو أفضل؟ نعم نستطيع!

▶ ️ انتقل إلى القسم التالي لتحديد كيفية تحسين التعقيد الزمني لاختبار الأعداد الأولية.

O (√n) خوارزمية للتحقق من الرقم الأولي في Python

يحدث أن عوامل العدد تحدث في أزواج.

إذا كان a أحد عوامل الرقم n ، فهناك أيضًا عامل b مثل axb = n ، أو ببساطة ، ab = n.

  كيفية البحث عن الجوز ومخاريط الصنوبر في 'معبر الحيوانات: آفاق جديدة'

دعنا نتحقق من ذلك من خلال مثال.

يوضح الجدول أدناه عوامل العدد 18 التي تحدث في أزواج. يمكنك التحقق من ذلك لعدد قليل من الأرقام إذا كنت ترغب في ذلك.

لاحظ أيضًا أن √18 تساوي 4.24 تقريبًا.

وفي العوامل التي تحدث في أزواج (أ ، ب) ، يمكنك أن ترى أنه إذا كانت أ أقل من 4.24 ، فإن ب أكبر من 4.24 – في هذا المثال ، (2 ، 18) و (3 ، 6).

عوامل العدد 18 في أزواج

يوضح الشكل أدناه عوامل 18 المرسومة على خط الأعداد.

إذا كان العدد n مربعًا كاملًا ، فسيكون لديك a = b = √n كأحد العوامل.

▶ ️ انظر إلى عوامل العدد 36 في الجدول أدناه. بما أن 36 مربعًا كاملًا ، فإن أ = ب = 6 هو أحد العوامل. بالنسبة لجميع أزواج العوامل الأخرى (أ ، ب) ، فإن أ <6 و ب> 6 تبقى ثابتة.

عوامل العدد 36 في أزواج

باختصار ، لدينا ما يلي:

  • يمكن كتابة كل رقم n كـ n = axb
  • إذا كان n مربعًا كاملًا ، فإن a = b = n.
  • وإذا كانت a n.
  • عدا ذلك ، إذا كانت a> b ، فإن a> n و b

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

كيفية تعديل خوارزمية is_prime () إلى O (√n)

دعنا ننتقل إلى تحسين الوظيفة للتحقق من الأعداد الأولية في Python.

import math
def is_prime(n):
  for i in range(2,int(math.sqrt(n))+1):
    if (n%i) == 0:
      return False
  return True

الآن ، دعنا نحلل تعريف الوظيفة أعلاه:

  • لحساب الجذر التربيعي لرقم ، دعنا نستورد وحدة الرياضيات المضمنة في بايثون ، ونستخدم الدالة math.sqrt ().
  • نظرًا لأن n قد لا يكون مربعًا كاملاً ، فسيتعين علينا تحويله إلى عدد صحيح. استخدم int (var) لتحويل var إلى int.
  • للتأكد من أننا نتحقق بالفعل حتى √n ، نضيف زائد واحد لأن الدالة range () تستبعد نقطة نهاية النطاق افتراضيًا.

تتحقق خلية الكود أدناه من أن وظيفتنا is_prime () تعمل بشكل صحيح.

is_prime(8)
# False

is_prime(15)
# False

is_prime(23)
# True

في القسم التالي ، دعنا ننشئ بعض المخططات البسيطة لفهم O (n) و O (n) بصريًا.

المقارنة بين O (n) و O (√n) بصريًا

▶ ️ قم بتشغيل مقتطف الشفرة التالي في بيئة دفتر ملاحظات Jupyter من اختيارك.

import numpy as np
import seaborn as sns
import pandas as pd


n = 20

x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)

يوضح المقتطف أعلاه كيف يمكنك رسم منحنيات n و √n لمجموعة من القيم.

  • نستخدم الدالة NumPy arange () لإنشاء مصفوفة من الأرقام.
  • وبعد ذلك ، نجمع قيم n و n حتى ، ولكن ليس بما في ذلك 20 ، في a الباندا DataFrame.
  • بعد ذلك ، نخطط باستخدام حطام البحر () وظيفة.

من المؤامرة أدناه ، نرى أن √n أصغر بكثير من n.

دعونا الآن نزيد النطاق إلى 2000 ونكرر نفس الخطوات المذكورة أعلاه.

import numpy as np
import seaborn as sns
import pandas as pd


n = 2000

x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)

من المخطط أعلاه ، يمكنك أن تستنتج أن خوارزمية O (√n) تكون أسرع بشكل ملحوظ عندما تختبر ما إذا كان عدد كبير أوليًا.

إليك مثال سريع: 2377 عدد أولي – تحقق من هذا! 😀

بينما يأخذ نهج O (n) ترتيب 2000 خطوة ، يمكن أن تساعد خوارزمية O (n) في الوصول إلى الإجابة في 49 خطوة فقط.

استنتاج

⏳ وحان الوقت للحصول على ملخص سريع.

  • للتحقق مما إذا كان الرقم أوليًا ، فإن الطريقة الساذجة هي إجراء حلقة عبر جميع الأرقام في النطاق (2 ، n-1). إذا لم تجد عاملًا يقسم n ، فإن n عدد أولي.
  • نظرًا لأن العامل الوحيد n أكبر من n / 2 هو n نفسه ، فقد تختار تشغيل حتى n / 2 فقط.
  • كلا النهجين أعلاه لهما تعقيد زمني لـ O (n).
  • نظرًا لحدوث عوامل العدد في أزواج ، يمكنك تشغيل ما يصل إلى √n فقط. هذه الخوارزمية أسرع بكثير من O (n). ويكون الكسب ملموسًا عند التحقق مما إذا كان عدد كبير أوليًا أم لا.

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

نراكم جميعا في برنامج تعليمي آخر. حتى ذلك الحين ، أتمنى لكم ترميزًا سعيدًا!