تعتبر خوارزمية Sieve of Eratosthenes من أسهل الخوارزميات لايجاد الاعداد الاولية Prime Numbers ضمن مجال معين من الاعداد الصحيحة n ، حيث تقوم فكرتها على حذف مضاعفات الاعداد داخل هذا المجال ، حيث أن تعريف الاعداد الاولية يستبعد وجود الاعداد التي يمكن ايجادها كحاصل ضرب عددين.
الخوارزمية من wikipedia
1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Strike from the list all multiples of p greater than p.
4. Find the first number remaining on the list greater than p (this number is the next prime); let p equal this number.
5. Repeat steps 3 and 4 until p^2 is greater than n.
6. All the remaining numbers on the list are prime.
مثال بسيط لايجاد الاعداد الاولية من 1 الى 100 (ملاحظة: العدد 1 لا يعتبر عدد اولي حيث أنه لا يوجد عددين مختلفين يقسما العدد 1) :
في البداية سننشئ مصفوفة من الاعداد :
سنبدأ من العدد الاولي 2 ، وسنقوم بازالة كل مضاعفاته ابتداءا من 4 :
ملاحظة: اللون الاخضر يعني عدد اولي ، اما الاحمر فهو ليس اولي.
العدد 3 هو أولي ، وسنحذف كل مضاعفاته ابتداءا من 9 :
نفس الشيء مع العدد 5 :
وكذلك العدد 7:
العدد التالي الان هو 11 ، لكن سنتوقف هنا لأن مربع العدد 11 أكبر من المجال المطلوب 100.
اذا الاعداد الاولية من 1 الى 100 هي :
مثال اخر :
تطبيق الخوارزمية :
هذا تطبيق بسيط للخوارزمية باستخدام سي++ ، والفكرة مشابهة تماما للمثال في الاعلي حيث سأنشئ مصفوفة من 100 عنصر ، وساضع جميع القيم فيها مساوية للواحد دلالة على أن كل العناصر هي اولية ، وبعدها عندما نجد عدد مركب Composite number وليكن i سنجعل قيمة العنصر i هي الصفر دلالة على انه تم حذف العنصر.
- CODE: تحديد الكل
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
void sieveOfEratosthenes(int N)
{
int* array = new int[N+1];
for (int i=2;i<=N;++i)
array[i] = 1;
array[1] = 0;
for (int i=2;i<=sqrt(N);++i) {
if (array[i] == 0)
continue;
for (int j=i*i;j<=N;j+=i) {
array[j] = 0;
}
}
for (int i=2;i<=N;++i)
if (array[i])
cout << i << " " ;
cout << endl;
delete [] array;
}
int main(int argc,char* argv[])
{
if (argc == 2)
sieveOfEratosthenes(atoi(argv[1]));
else
sieveOfEratosthenes(100);
return 0;
}
شرح بسيط :
- CODE: تحديد الكل
int* array = new int[N+1];
for (int i=2;i<=N;++i)
array[i] = 1;
array[1] = 0;
هنا تم انشاء المصفوفة وتعيين القيمة 1 لكل الاعداد دلالة على انها اولية ، اما العدد 1 فتم تعيين القيمة 0 له دلالة على انه ليس عدد أولي.
- CODE: تحديد الكل
for (int i=2;i<=sqrt(N);++i) {
if (array[i] == 0)
continue;
for (int j=i*i;j<=N;j+=i) {
array[j] = 0;
}
}
لا يوجد داعي لأن نمر على جميع الاعداد من 1 الى 100 ! سنبدأ من العدد 2 لان العدد 1 قد ذكرنا بأنه ليس اولي ، وسننتهي عند العدد 10 (تأتي من تطبيق الجذر التربيعي على n) لانه عنما تعمل الخوارزمية على العدد 2 و 3 و 5 و 7 و9 ستجد اننا قد مررنا على كل الاعداد(المضاعفة) في هذا المجال.
في البداية سيتم اختبار هل العدد ليس اولي ؟ اذا كانت الاجابة لا فهذا يعني أن العدد اولي ويجب معرفة مضاعفاته لكي نقوم بازالتها .
اما اذا كانت الاجابة نعم فهذا يعني ان هذا العدد مضاعف Composite number وبالتأكيد مضاعفات هذا العدد هي ليس أولية وقد تم ازالتها من قبل.
نتيجة البرنامج :
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
وهذا تطبيق اخر للدالة :
- CODE: تحديد الكل
void sieveOfEratosthenes(int N)
{
int* array = new int[N+1];
for (int i=2;i<=N;++i)
array[i] = 1;
array[1] = 0;
for (int i=2;i<=N/2;++i)
for (int j=2;j<=N/i;++j) {
cout << i*j << endl;
array[i*j] = 0;
}
for (int i=2;i<=N;++i)
if (array[i])
cout << i << " " ;
cout << endl;
delete [] array;
}
واي سؤال يرحب به..
مصادر:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://en.wikipedia.org/wiki/Prime_number
http://www.algolist.net/Algorithms/Numb ... atosthenes
كتاب Algorithms in C.
الكود بالمرفقات.
بالتوفيق.
