هل يوجد خوارزمية فعالة للتأكد إن كان العدد أولي

ﻻ يوجد قانون لحساب العدد الاولي ولكن يوجد طرق أكثر فاعلية من المرور من الرقم 2 حتى الرقم س , ولكن دعنا نضع الإثبات الرياضي التالي أولاً حتى نستوعب الطريقة بشكلٍ أفضل

دعنا نرمز للرقم المُراد معرفة إن كان أولي بالرمز س
دعنا نفترض عددين  أ, و ب
إن كان أ>جذر س
و ب > جذر س
إذاً أ*ب > س
            
مما سبق نستنتج أن ﻻ يمكن أن يكون أ و ب أكبر من س

الإستنتاج السابق يُبت لنا أن ﻻ يمكن أن يكون للعدد أعداد يقبل القسمة عليها أكبر من جذرهِ التربيعي

بالتالي يمكننا تحسين الخوارزمية بدلاً من المرور بدءاً من الرقم 2 حتى العدد س , أن نقوم بالمرور بدءاً من العدد 2 حتى الجذر التربيعي للعدد س

وبالتالي يتم تقليل التعقيد الوقتي(time complexity) للخوارزمية لتتحول من O(n) إلى O(sqrt(n)) 

ويمكنك معرفة المقصود بالتعقيد الوقتي بشكل أكبر من خﻻل المقالة المرفقة

نعم يوجد، ويمكنك تحديد أي عدد إذا كان أوليَاً أم لا اعتماداً على التعريف "العدد الأولي هو عدد طبيعي أكبر قطعاً من 1، لا يقبل القسمة إلا على نفسه وعلى واحد فقط. " وفي البرمجة هناك نهجين أساسيين الأول تعقيده O(n^2):

def isPrime(x):
  # إذا كان العدد أصغر أو يساوي الواحد فهو ليس أولي حسب التعريف
  if x <= 1:
    return False
  else:
    # [2,x/2] نبحث عن وجود أي قاسم للعد ضمن المجال التالي 
	  for i in range(2, int(x/2)+1):
     # إذا وجدنا أي قاسم له ضمن هذا المجال، فهذا يعني أنه ليس أولي 
	  	if (x % i) == 0:
		  	return False
		  	
	  # وأخيراً إن لم يجد أي قاسم، فهذا يعني أنه أولي
  return True
# تجربته
isPrime(5) # True   
isPrime(1) # False  ليس أولي
isPrime(11) # True  أولي
isPrime(6) # False
isPrime(15) # False
isPrime(23) # True

النهج الثاني يعتمد على نظرية الأعداد حيث سنقوم بالبحث ضمن مجال أضيق وهو من 2 إلى جذر العدد فلايمكن أن تجد قاسم لعدد ما أكبر من جذره، وهذا ماسيحسن تعقيد الخوارزمية من n^2 إلى جذر ال n:

def isPrime(x):
  from math import sqrt
  # إذا كان العدد أصغر أو يساوي الواحد فهو ليس أولي حسب التعريف
  if x <= 1:
    return False
  else:
    # 1+هنا سنغير المجال الذي سنبحث فيه عن وجود قاسم حيث أن المجال هو من 2 إلى جذر العدد
    for i in range(2, int(sqrt(x)) + 1):
      if (x % i == 0):
        return False # ليس أولي
  return True

# تجربته
isPrime(5) # True   أولي
isPrime(1) # False   غير أولي
isPrime(11) # True
isPrime(6) # False
isPrime(15) # False
isPrime(23) # True

في حال أردن التعامل مع عدد كبير من الاستعلامات (أي ليس عدد واحد فقط، بل مئات الاستعلامات) يمكن حساب الأعداد الأولية جميعها وتخزينها في مصفوفة ثم فقط التأكد من أن هل العدد المطلوب هو أولي أم لا باستعمال خوارزيمة Sieve.

1. نفرض أن كل الأعداد أولية بتعريف مصفوفة قيمها True
2. نقوم بالمرور على المصفوفة وكل عدد أولي ستكون مضاعفاته بالتأكيد غير أولية، لذلك نعمل حلقة ونبدل مضاعفات العدد الحالي لتصبح غير أولية أي تعديل جميع المضاعفات ل False

const int N = 10000100;
bool pno[N];

void SieveOfEratosthenes() {
   
   memset(pno, true, sizeof(pno));

   for (int i = 2; i*i< = N; i++) {
      if (pno[i] == true) {
         for (int j = i*2; j< = N; j + = i) // المرور على مضاعفات العدد وتعليمها كغير أولية
         	pno[j] = false;
      }
   }
}

للاختبار، هل العدد n أولي أم لا نتأكد من قيمة دليله في المصفوفة فقط، نحسب الأعداد جميعهم مرة واحدة ثم عملية التحقق تتم بلحظة.

SieveOfEratosthenes(); // استدعاء الدالة


int n;
cin >> n;

cout << pno[n] << " ";

وتعقيد هذه الخوارزمية سريع جداً، 

بتاريخ On 26‏/9‏/2021 at 16:53 قال Ali Haidar Ahmad:

نعم يوجد، ويمكنك تحديد أي عدد إذا كان أوليَاً أم لا اعتماداً على التعريف "العدد الأولي هو عدد طبيعي أكبر قطعاً من 1، لا يقبل القسمة إلا على نفسه وعلى واحد فقط. " وفي البرمجة هناك نهجين أساسيين الأول تعقيده O(n^2):

def isPrime(x):
  # إذا كان العدد أصغر أو يساوي الواحد فهو ليس أولي حسب التعريف
  if x <= 1:
    return False
  else:
    # [2,x/2] نبحث عن وجود أي قاسم للعد ضمن المجال التالي 
	  for i in range(2, int(x/2)+1):
     # إذا وجدنا أي قاسم له ضمن هذا المجال، فهذا يعني أنه ليس أولي 
	  	if (x % i) == 0:
		  	return False
		  	
	  # وأخيراً إن لم يجد أي قاسم، فهذا يعني أنه أولي
  return True
# تجربته
isPrime(5) # True   
isPrime(1) # False  ليس أولي
isPrime(11) # True  أولي
isPrime(6) # False
isPrime(15) # False
isPrime(23) # True

النهج الثاني يعتمد على نظرية الأعداد حيث سنقوم بالبحث ضمن مجال أضيق وهو من 2 إلى جذر العدد فلايمكن أن تجد قاسم لعدد ما أكبر من جذره، وهذا ماسيحسن تعقيد الخوارزمية من n^2 إلى جذر ال n:

def isPrime(x):
  from math import sqrt
  # إذا كان العدد أصغر أو يساوي الواحد فهو ليس أولي حسب التعريف
  if x <= 1:
    return False
  else:
    # 1+هنا سنغير المجال الذي سنبحث فيه عن وجود قاسم حيث أن المجال هو من 2 إلى جذر العدد
    for i in range(2, int(sqrt(x)) + 1):
      if (x % i == 0):
        return False # ليس أولي
  return True

# تجربته
isPrime(5) # True   أولي
isPrime(1) # False   غير أولي
isPrime(11) # True
isPrime(6) # False
isPrime(15) # False
isPrime(23) # True

 

ارغب بحساب خوارزمية جمع عددين اوليين مع المخطط التدفقي لها ارجو مساعدتي لانني احتاجها لامتحاني