• 0
Skeptic Iriban

خوارزمية جديدة للأعداد الأولية " الحقوق محفوظه للناشر "

سؤال

بسم الله الرحمن الرحيم 

السلام عليكم ورحمه الله وبركاته 

أعضاء المنتدى الجميل 

أقدم لكم اليوم خورزمية لحساب الاعداد الاولية و هي مبتكرة  " غير موجودة على شبكة الويب و من اختراعي :P :P " 

نعرف أن العدد الاولي هو : 

العدد الأولي هو عدد طبيعي أكبر قطعا من 1، لا يقبل القسمة إلا على نفسه وعلى الواحد فقط 

و بما أنكم مبرمجين فتعتمدون على خوارزميات في ايحاد الاعداد الاولية و منها : 

1. القسمة المتكررة : الطريقة الأكثر بساطة، والأكثر سهولة من حيث الفهم، من أجل تحديد أولية عدد ما تدعى القسمة المتكررة. تتمثل هاته الطريقة في قسمة العدد n على جميع الأعداد الصحيحة الأكبر من الواحد والأصغر من الجذر التربيعي ل n. إذا لم تنتج إحدى هذه القسمات باقيا، فإن العدد n ليس بالأولي. وهو أولي في غير ذلك. 

2. الغرابيل : كل خوارزمية تمكن من إيجاد جميع الأعداد الأولية الأصغر من عدد ما تسمى غربالا. أقدم مثال على ذلك غربال إراتوستينس لكنه لا يستعمل إلا في حالة الأعداد الصغيرة. غربال أتكينأحدث منه ولكنه أكثر منه تعقيدا ولهذا فهو أكثر منه سرعة.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

أنا اختلفت بالتعريف و من خلال تعريف مطور للقسمة المتكررة و الغرابيل توصلت لخوارزمية و هي كالتالي : 

أولا : العدد الاولي : هو العدد الذي " لا " يقبل القسمة على " جميع " الاعداد الاولية التي تساوي "و" تسبق الجذر التربيعي له . " تعريف معقد " 

بالمثال يتضح المقال : 

نفترض انه لدينا العدد 30 لكي نعرف انه اولي نقوم بالآتي : 

1. نحسب الجذر التربيعي له و هو 5.4 تقريبا . 

2. نقوم بقسمة العدد على ( "2" ) يقبل القسمة على 2 اذا ليس أولي . 

نفترض أن لدينا العدد 31 لكي نعرف انه اولي نقوم بالتالي : 

1. نحسب الجذر التربيعي له و هو 5.4 تقريبا .  

2. نقوم بقسمة العدد على ("2") لا يقبل القسمة 

3. نقوم بقسمة العدد على ("3") لا يقبل القسمة 

4. نقوم بقسمة العدد على ("5") لا يقبل القسمة 

اذا العدد 31 هو عدد اولي . 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

يمكن بسهولة ايجاد الاعداد الاولية عن طريق اعطاء كل عدد اولي ID حتى نتمكن من الحصول عليه مرة أخرى عن طريق تسجيل العدد و ID بقاعده بيانات او مصفوفة 

و يتم معرفة العدد الاولي بسهولة تامه عن طريق حساب الجذر التربيعي له و حساب Mod "الباقي" لقسمته على جميع الاعداد الاولية التي تسبق جذره التربيعي .. 

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

للآسف انا ضعيف في لغات البرمجه الحديثه ، و متأسف على عدم ارفاق اي كود برمجي و لكن اعتقد ان الخوارزمية واضحه .. 

وأي استفسار أنا جاهز ... و شكرا لكم 

أرجو الدعاء لي بالتوفيق :) 

الحقوق محفوظة للناشر 

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

13 إجابة على هذا السؤال .

  • 0

أهلاً أخي ..

في علم الخوارزميات .. هناك شيء اسمه "التعقيد الزمني " أي .. كم تستغرق الخوارزمية لتنجز عملها بالنسبة للمدخلات

للأسف خوارزميتك ليست جديدة :) ولكن هذا لا يعني أن تحبط .. بالعكس .. فقد اكتشفتها بنفسك :)

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

التحسين الممكن للخوارزمية هو اختبارها على الأعداد الأصغر أو تساوي جذر الرقم n  .. وهنا نقول أن التعقيد الزمني أصبح(( O(sqrt(n  وهو تحسين كبير ..

الخوارزمية التي تحدثت عنها تختبر على الأعداد الأولية فقط الأصغر من جذر الرقم n  .. وحسب نظرية الأعداد الأولية فإن عدد الأعداد الأولية الأصغر من n  هو تقريباً( n/ln(n

أي أنك ستختبر(( sqrt(n)/ln(sqrt(n والذي يؤول إلى :

2*(sqrt(n مقسوماً على( ln(n ولكن من المعلوم أن اللوغاريتم قيمته صغيرة .. فلوغاريتم عدد مكون من 100 منزلة تقريباً 100

لذلك .. صحيح أن الخوارزمية التي طرحتها جيدة , ولكنها لا تقدّم الكثير من التحسين ..

وحقوق النشر غير محفوظة :D

 

بالتوفيق

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

بس يا اخي لو توضيح اكتر للتعقيد الزمني ... يعني الخوارزمية بتقدم تحسين على القسمة المتكررة بمعنى انو لو عايز اعرف جميع الاعداد الاولية اللي تحت 100 محتاج اقسمهم على 2 ، 3 ،5،7 اربع ارقام فقط و ليس ما يقارب 10 كما في القسمه المتكررة نفسها ... و اعتقد على أرقام كبيرة رح تجد فارق

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم ...

هذا كود الخوارزمية ..

#include<stdio.h>#include<stdlib.h>#include <math.h>#define MAX 1000#define MAX_NUMBER 5000int main(){	int a[MAX];	int i , j , count = 0;	short is_prime;	double sq;	for(i = 2 ; i < MAX_NUMBER ; i ++)	{		sq = sqrt(i);		is_prime = 1 ;		for(j = 0; j < count  ; j++)		{			if (a[j] > sq) break;			if( i % a[j] == 0)			{				is_prime = 0;				break;			}		}		if (is_prime == 1)		{			a[count] = i;			count ++;		}	}	for(i = 0 ; i < count ; i ++)	{		printf("%d \n" , a[i]);	}return 0;}
2

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أخي صحيح أنك ستقوم بعمليات قسمة أقل , ولكنك ستقوم بغربلة وهذه وحدها كافية لتكون الخوارزمية أبطأ , (في حال أردنا اختبار عدد واحد فقط )

الخوازرمية التي طرحتها مفيدة في حال احتجنا اختبار الكثير من الأعداد , وليس عدداً واحداًَ ..

ولكن بما أنك قد طرحت الموضوع بهذه الطريقة , فلماذا لم تفكّر في غربلة جميع الأعداد (الأصغر من  1000000مثلاً ) وبهذا ستحصل على جميع الأعداد الأولية ويمكنك تخزينها

وعندما تريد اختبار عدد ما إن كان أولياً .. يمكنك ببساطة التأكد من كونه موجوداً في القائمة السابقة ..

____________________________

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

 

كما ذكرت لك .. اكتشافك للطريقة دليل على مستقبل مشرق في مجال الرياضيات وأنصحك بالقراءة باللغة الانكليزية وخصوصاً من ويكيبيديا فهي تعطيك لمحة وافية عن أي موضوع ترغب بالبحث عنه ..

وفقك الله

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم ...

شكرا للاخ مصطفى على المشاركة ...

شكرا لك أخي Skeptic Iriban ...  

حقيقة ... تحسب لك أنك استطعت "اكتشاف" هذه الطريقة للأعداد الأولية ...بلا شك ان عندك مقدرة جيدة على التحليل "الرقمي" ....

و لكن تؤخذ عليك أنك لم تقرأ عن الموضوع باللغة الانكليزية  (كما قال الأخ مصطفى) ...

فكرتك معروقة سابقا و هي باسم : "Using Only Primes As Divisors" و هي منشورة في مقالة : "Fun With Prime Numbers"  

استمر في محاولات جديدة ... 

 

Which is the fastest algorithm to find prime numbers?

2

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

المشكله انو انا حاليا بدرس تخصص طب بشري يعني الخوارزمية اجت فكرة على راسي و ما لحقت اشوف النت و اقرا حول الاعداد الاولية لانو تخصص الطب ضغط كبيير ، انا كنت حابب ادرس تخصص علوم حاسب و اخيرا استطعت اقناع والدي بتخصص علوم الحاسب ، بس رح اكمل السنة هاي طب و ابحث حاليا عن اي منحة لدول اجنبية  .. ادعولي بالتوفيق و تنحل مشكلتي العسيرة .. 

بشكر مرورك : 

مصطفى 36a2  حسام الشامي
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

بالتوفيق ... 

و نرجو أن لا تتسرع في الانتقال لعلوم الحاسب ...

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

وأنا من جهتي أنصحك بـSPOJ ...
شكرا لك لقبول نصيحتي

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

لا أريد أن أتفلسف

ولكن كما قال الأخ حسام لا تتسرع بترك الطب والاتجاه إلى علوم الحاسب

يمكنك جعلها هواية لك تستثمر فيها وقت الفراغ .. خصوصاً أن معظم الطب حفظ , بينما معظم الرياضيات تفكير .. وبذلك لن يتعب دماغك :)

بالنسبة لي أن اختصاصي الكترون واتصالات .. وكذلك الأخ keep forward ولكن البرمجة والخوارزميات هوايات .. (صحيح أنها تأخذ معظم الوقت  .. ولكنني لا أزال محسوب على اختصاصي )

 

فكر مليّاً .. فقرار ترك الطب أمر خاطئ بنسبة 97% :D

وفقك الله لما فيه مصلحتك

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

اوك .. اكيد رح اعمل بنصيحتك اخي Keep Forward و بتشكرك على النصيحه الجميله .. 

اخي مصطفى اسمحيلي انو اعارضك بقصه انو خباري بنسبة 97% خاطئ و الرد برساله على البرايفت ^_^ 

متــــــــــــــــــشكر على مروركم و الحقوق بالاعلى ليست محفوظه لي و متأسف على التسرع بالحكم .... 

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

بالتوفيق

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

سلام 

 

مدري وش الموضوع لكن شدتني الردود الاخيره.

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

بالنسب لتغيير التخصص لو كنت طبيب وعندك المام بالخوارزميات راح يكون باستطاعتك عمل اشياء ولايحلم اي حاسوبي بعملها.

 

اذا مصمم ادرس رياضيات افضل..

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .