مقالات

2.1: منخل إراتوستينس - الرياضيات


الشرط هو عدد صحيح أكبر من 1 لا يقبل القسمة إلا على 1 وعلى نفسه. الأعداد الصحيحة 2 ، 3 ، 5 ، 7 ، 11 هي أعداد صحيحة أولية. لاحظ أن أي عدد صحيح أكبر من 1 وليس عددًا أوليًا يُقال إنه a مركب عدد.

منخل إراتوستينس

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

كل عدد صحيح أكبر من واحد له قاسم أولي.

نقدم الدليل على هذا Lemma بالتناقض. افترض أن هناك عددًا صحيحًا أكبر من واحد لا يحتوي على قواسم أولية. نظرًا لأن مجموعة الأعداد الصحيحة التي تحتوي على عناصر أكبر من واحد بدون قواسم أولية غير فارغة ، فبموجب مبدأ الترتيب الجيد يوجد أقل عدد صحيح موجب (n ) أكبر من الذي لا يحتوي على قواسم أولية. وبالتالي (n ) مركب منذ (n ) يقسم (n ). ومن هنا [n = ab mbox {with} 1

إذا كان (n ) عددًا صحيحًا مركبًا ، فإن n له عامل أولي لا يتجاوز ( sqrt {n} ).

بما أن (n ) مركب ، إذن (n = ab ) ، حيث (a ) و (b ) عدد صحيح مع (1 sqrt {n} ) ، ثم

[ sqrt {n}

و كنتيجة

[ab> sqrt {n} sqrt {n} = n. ]

لذلك (a leq sqrt {n} ). أيضًا ، من خلال Lemma 3 ، يجب أن يكون (a ) مقسومًا أوليًا (a_1 ) وهو أيضًا قاسم أولي لـ (n ) وبالتالي فإن هذا القاسم أقل من (a_1 leq a leq sqrt {ن}).

نقدم الآن خوارزمية غربال إراتوستينس المستخدمة لتحديد الأعداد الأولية حتى عدد صحيح معين.

خوارزمية منخل إراتوستينس

  1. اكتب قائمة الأرقام من 2 إلى أكبر رقم (n ) تريد اختباره. لاحظ أن كل عدد صحيح مركب أقل من (n ) يجب أن يحتوي على عامل أولي أقل من ( sqrt {n} ). ومن ثم يتعين عليك شطب مضاعفات الأعداد الأولية الأقل من ( sqrt {n} )
  2. اشطب كل مضاعفات 2 الأكبر من 2 من القائمة. الرقم الأول المتبقي في القائمة هو عدد أولي.
  3. اشطب كل مضاعفات هذا الرقم من القائمة.
  4. كرر الخطوات المذكورة أعلاه حتى لا يتم العثور على المزيد من المضاعفات للأعداد الصحيحة الأولية الأقل من ( sqrt {n} )

تمارين

  1. استخدم منخل إراتوستينس لإيجاد كل الأعداد الأولية الأقل من 100.
  2. استخدم غربال إراتوستينس لإيجاد كل الأعداد الأولية الأقل من 200.
  3. بيّن أنه لا يوجد عدد صحيح من النموذج (أ ^ 3 + 1 ) عدد أولي باستثناء (2 = 1 ^ 3 + 1 ).
  4. أظهر أنه إذا كان (2 ^ n-1 ) عددًا أوليًا ، فسيكون (n ) أوليًا.
    تلميح: استخدم الهوية ((a ^ {kl} -1) = (a ^ {k} -1) (a ^ {k (l-1)} + a ^ {k (l-2)} +. .. + أ ^ ك + 1) ).

نظرية المنخل

نظرية المنخل هي مجموعة من التقنيات العامة في نظرية الأعداد ، مصممة للعد ، أو بشكل أكثر واقعية لتقدير حجم ، مجموعات منخل من الأعداد الصحيحة. المثال النموذجي للمجموعة التي تم غربلتها هو مجموعة الأعداد الأولية التي تصل إلى حد معين X. في المقابل ، فإن المثال النموذجي للغربال هو منخل إراتوستينس ، أو منخل ليجيندر الأكثر عمومية. الهجوم المباشر على الأعداد الأولية باستخدام هذه الأساليب سرعان ما يصل على ما يبدو إلى عقبات لا يمكن التغلب عليها ، في طريق تراكم مصطلحات الخطأ. [ بحاجة لمصدر ] في أحد الخيوط الرئيسية لنظرية الأعداد في القرن العشرين ، تم العثور على طرق لتجنب بعض صعوبات الهجوم الأمامي بفكرة ساذجة لما يجب أن يكون عليه الغربلة. [ بحاجة لمصدر ]

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


ولفرام موارد الويب

الأداة رقم 1 لإنشاء العروض التوضيحية وأي شيء تقني.

استكشف أي شيء باستخدام محرك المعرفة الحسابي الأول.

استكشف آلاف التطبيقات المجانية في مجالات العلوم والرياضيات والهندسة والتكنولوجيا والأعمال والفن والتمويل والعلوم الاجتماعية والمزيد.

انضم إلى مبادرة تحديث تعليم الرياضيات.

حل التكاملات مع ولفرام | ألفا.

تصفح مسائل الواجب المنزلي خطوة بخطوة من البداية إلى النهاية. تساعدك التلميحات على تجربة الخطوة التالية بنفسك.

مشاكل وإجابات تمارين عشوائية غير محدودة مع حلول مدمجة خطوة بخطوة. تدرب على الإنترنت أو قم بعمل ورقة دراسة قابلة للطباعة.

مجموعة من أدوات التدريس والتعلم التي صممها خبراء التعليم في Wolfram: كتاب مدرسي ديناميكي ، وخطط الدروس ، وعناصر واجهة المستخدم ، والعروض التوضيحية التفاعلية ، والمزيد.


هل يمكن لمنخل إراتوستينس بناء طلاقة دائمة؟

على المدى حقائق الرياضيات هو في الواقع حيوان أليف يزعجني. يجعلني أفكر في التدريبات والتكرار والاختبارات المحددة بوقت. أنا أفضل التفكير في الحساب والطلاقة. إذا كانت الطالبة لا تعرف & # 8217t أن 6 & # 2154 هي 24 ، أريدها أن تدرك أنها & # 8217s 4 أكثر من 5 & # 2154. حتى لو كان ذلك يعني تخطي العد أو استخدام أصابعها ، فمن الأفضل استخدام الاستراتيجيات المفاهيمية بدلاً من الجلوس وحفظ قائمة. قائمة & # 8217ll ستنسى بمجرد انتهاء الاختبار.

بالإشارة إلى الطلاقة من حيث & # 8216 حقائق & # 8217 يشعر فقط بعدم الاتصال. أريد أن يتقن الطلاب من خلال تطوير الإحساس بالأرقام. الجمع هو عكس الطرح. الضرب هو الجمع المتكرر. للعد بالتسعات ، قم بزيادة خانة العشرات بمقدار واحد ، وتقليل خانة الآحاد بمقدار واحد.

هذا هو المكان الذي يأتي فيه المنخل. عملية التلوين في الأنماط تخلق فهمًا قويًا للصلات. إذا عدت بمقدار 7 خمس مرات ، فسأصل إلى 35. لا يزال العد التنازلي من 35 × 7 & # 8217 يأخذ 5 خطوات. واو ، أعتقد أن الضرب والقسمة يجب أن يكونا متصلين!

إذا أردت إضافة 77 + 8 ، يمكنني الانتقال بصف واحد لأسفل (+10) ومربعين على اليسار (-2). هذا & # 8217s اختصار مفيد & # 8217 سأتذكر في المرة القادمة التي & # 8217m أقوم فيها بالرياضيات العقلية.

عندما يتعلم الطلاب & # 8216 حقائق & # 8217 في السياق ، فإنه يجعل الرياضيات أكثر إثارة للاهتمام. إنها أيضًا طريقة قوية لمساعدتهم على تذكر ما تعلموه & # 8217 & # 8212 حتى بعد العطلة الصيفية التالية.


ابحث عن الأعداد الأولية باستخدام غربال إراتوستينس

منخل إراتوستينس هي خوارزمية بسيطة وقديمة (عمرها أكثر من 2200 عام) تستخدم للعثور على الأعداد الأولية حتى أي حد معين. إنها إحدى أكثر الطرق فاعلية للعثور على الأعداد الأولية الصغيرة (& lt = $ 10 ^ 8 $).

بالنسبة لحد أعلى معين ، تعمل الخوارزمية عن طريق تعليم مضاعفات الأعداد الأولية بشكل متكرر كمركب ، بدءًا من 2. بمجرد تمييز جميع مضاعفات العدد 2 كمركب ، يتم وضع علامة على الموليبلات الخاصة بالعدد الأولي التالي ، أي 3 ، على أنها مركبة. تستمر هذه العملية حتى $ p & lt sqrt (N) $ حيث يكون عددًا أوليًا.

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

غربلة الاثنين وغربلة الثلاثة ،
منخل إراتوستينس.
عندما تسامي المضاعفات ،
الأعداد المتبقية هي Prime.

كود مزيف

الكود الكاذب لمنخل خوارزمية إراتوستينس هو كما يلي:

مثال

أوجد قائمة الأعداد الأولية من 2 إلى 20

مثال مرئي

تعقيد

يكون تعقيد الوقت والمكان لخوارزمية The Sieve of Eratosthenes كما يلي:

  • صعوبة وقت الحالة الأسوأ: Θ (N سجل تسجيل N)
  • متوسط ​​تعقيد وقت الحالة: Θ (N سجل تسجيل N)
  • أفضل تعقيد لوقت الحالة: Θ (N سجل تسجيل N)
  • تعقيد الفضاء: Θ (N)

تطبيقات

تطبيقات خوارزمية Sieve of Eratosthenes في 9 لغات مختلفة وهي C و C ++ و C Sharp و Java و Go و Haskell و JavaScript و PHP و Python.


قائمة / مخطط / التاريخ (الخلفية) للأرقام الأولية

كان علماء الرياضيات اليونانيون القدماء أول من درس على نطاق واسع الأعداد الأولية وخصائصهم. اهتم علماء الرياضيات في مدرسة فيثاغورس (500 قبل الميلاد إلى 300 قبل الميلاد) الأعداد الأولية لخصائصها الصوفية والعددية. لقد فهموا فكرة البدائية وكانوا مهتمين بالأرقام المثالية والودية.

في 300 قبل الميلاد ، عندما ظهرت Euclid & # 39s Elements ، ظهرت عدة نتائج مهمة حول الأعداد الأولية تم إثباتها. يوضح دليل إقليدس للنظرية الأساسية في الحساب أن & ldquo يمكن كتابة كل عدد صحيح كمنتج لـ الأعداد الأولية بطريقة فريدة rdquo و.

في عام 200 قبل الميلاد ، ابتكر اليوناني إراتوستينس خوارزمية للحساب الأعداد الأولية، والتي تسمى في العصر الحديث غربال إراتوستينس.

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

في عام 1952 ، ثبت أن أرقام ميرسين أولية بواسطة روبنسون باستخدام كمبيوتر مبكر وبدأ العصر الإلكتروني.

بحلول عام 2018 ، تم العثور على ما مجموعه 50 من أعداد ميرسين الأولية.

كان لعمل أويلر تأثير كبير على نظرية الأعداد بشكل عام وما إلى ذلك الأعداد الأولية خاصه.

التوأم رئيس الوزراء

تُعرف الأرقام الأولية التي تختلف بمقدار 2 بالأرقام التوأم الأولية
على سبيل المثال ، يتم عرض قائمة بالأرقام الأولية بين 1 إلى 10 أدناه ،

دعونا ننظر في أول رقمين أوليين في خط الأعداد أعلاه.
إنها 2 و 3.
الفرق بين 2 و 3 هو 1 (3-2 = 1)
وبالتالي ، 2 و 3 ليسا رقمين رئيسيين توأمين

دعونا نفكر في الزوج الثاني من الأعداد الأولية في خط الأعداد المحدد.
إنها 3 و 5.
الفرق بين 3 و 5 هو 2 (5 - 3 = 2)
ومن ثم ، فإن الرقمين 3 و 5 هما رقمان رئيسيان مزدوجان

وبالمثل ، دعونا نحاول مع الزوج الثالث من الأعداد الأولية في خط الأعداد المحدد.
إنها 5 و 7.
الفرق بين 5 و 7 هو 2 (7 - 3 = 2)
ومن ثم ، فإن 5 و 7 هما رقمان رئيسيان مزدوجان

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

الأعداد الأولية المشتركة

الأعداد الأولية المشتركة هي مجموعة من الأعداد التي لها 1 فقط كعامل مشترك. Co تعني رقمين ، وبالتالي من أجل تحديد الأعداد الأولية المشتركة ، سنحتاج إلى رقمين.
على سبيل المثال
دعونا نفكر في زوج العددين 18 و 35.
18 يمكن كسرها أو بعبارة أخرى يمكن كتابتها كمنتج لرقمين على النحو التالي ،
1 × 18 = 18
2 × 9 = 18
3 × 6 = 18
6 × 3 = 18
9 × 2 = 18
18 × 1 = 18
من قائمة حاصل ضرب عددين أعلاه ، عوامل 18 هي 1 و 2 و 3 و 6 و 9 و 18

دعونا نحسب نفس الشيء للرقم 35 ، وهو رقم الاقتران مع 18 في البيان المعطى.
35 يمكن كسرها أو بعبارة أخرى يمكن كتابتها كمنتج لرقمين على النحو التالي ،
1 × 35 = 35
5 × 7 = 35
7 × 5 = 35
35 × 1 = 35
من قائمة حاصل ضرب عددين أعلاه ، عوامل 35 هي 1 و 5 و 7 و 35

بمقارنة عاملي 18 و 35 ، يبدو أن الرقم 1 هو العامل المشترك الوحيد ، وبالتالي يفي بخاصية زوج من الأرقام التي يطلق عليها أرقام Co-Prime.

دعنا نعمل على مجموعة أخرى من الأرقام لتحديد الفرق بين الأرقام الأولية المشتركة والأرقام غير الأولية.
في هذه الحالة ، لنأخذ 18 و 19
النتيجة كما هو موضح في الصورة أدناه ،

نظرًا لأن العامل المشترك الوحيد للأرقام 18 و 19 هو 1 ، يمكن تسمية الرقمين 18 و 19 على أنهما الأعداد الأولية المشتركة.

مثال آخر،
في هذه الحالة ، لنأخذ 18 و 20
على الرغم من أن 1 هو عامل مشترك بين 18 و 20 ، إلا أن هناك عاملًا مشتركًا آخر في القائمة وهو الرقم 2.


خاصية رقم Co-Prime هي أنه يجب أن يحتوي على 1 فقط كعامل مشترك. في هذه الحالة ، لدينا أيضًا 2 مع 1 كعامل مشترك ، وبالتالي فإن الرقمين 18 و 20 ليسا رئيسيين بطبيعتهما.

حقيقة مثيرة للاهتمام حول 1 هي أنه رقم أولي مشترك لجميع الأرقام.


2.1: منخل إراتوستينس - الرياضيات

يمكن القول أن إراتوستينس معروف على نطاق واسع بأنه عالم رياضيات يوناني مشهور. ما لا يعرفه معظم الناس على الأرجح هو أن إراتوستينس ليس فقط عالم رياضيات مشهورًا ولكنه أيضًا جغرافي وعالم فلك ومؤرخ معروف.

قبل أن أخوض في بعض إنجازاته ، دعني أخبرك قليلاً عن تاريخه الشخصي. وُلِد إراتوستينس في مدينة قورينا في شمال إفريقيا عام 276 قبل الميلاد ، والتي تُعرف الآن باسم ليبيا ، ويُعتقد أنه جوع نفسه حتى الموت عام 195 قبل الميلاد. بسبب إصابته بالعمى ولم يعد بإمكانه العمل. عندما كان شابًا ، درس إراتوستينس في أثينا. في النهاية ، صنع مثل هذا الاسم لنفسه في مجالاته العديدة التي لفتت انتباه حاكم مصر ، بطليموس الثالث. دعا بطليموس الثالث إراتوستينس إلى الإسكندرية ، مصر لسببين لتعليم ابنه ولأن يكون أمين مكتبة جامعة الإسكندرية العظيمة. انتهز إراتوستينس الفرصة. في الجامعة ، كان قادرًا على الاهتمام به على الأكثر والمشاركة مع علماء آخرين. الآن إلى إنجازاته. . .

أحد إنجازاته الرئيسية في الرياضيات هو إنشاء غربال يحدد الأعداد الأولية حتى أي حد معين. لا يزال هذا الغربال ، الذي يسمى غربال إراتوستينس ، مهمًا حتى اليوم في نظرية بحث الأرقام. الأعداد الأولية هي الأعداد الطبيعية أكبر من 1 والتي يمكن تقسيمها دون باقي فقط بنفسها وعلى 1. اكتشف إراتوستينس أنه إذا كنت ستكتب جميع الأعداد الطبيعية من 2 إلى اللانهاية و "غربال" كل رقم ثاني بعد اثنين ( أو مضاعفات الرقمين) ، ثم انتقل إلى الرقم المتاح التالي (3) واستمر في "غربلة" كل مضاعف لـ 3 وما إلى ذلك ، سينتهي الأمر بقائمة من الأعداد الأولية.

يُعرف إراتوستينس أيضًا بإنجازاته في علم الفلك. حاول العديد من علماء الفلك والرياضيات قبل وبعد إراتوستينس قياس محيط الأرض بدقة ، ولكن كان إراتوستينس هو الذي جاء من خلاله. وجد محيط الأرض ما يقرب من 250000 ملعب (25000 ميل). لاحظ إراتوستينس أن الشمس تشرق مباشرة أسفل بئر في وقت الظهيرة في يوم الانقلاب الصيفي في سيناء ، وأنها ألقت بظلالها على الإسكندرية ، جنوب مكان البئر مباشرة. لحساب محيط الأرض ، قاس إراتوستينس زاوية الظل على الأرض. حتى أدرك إراتوستينس ذلك ، كان يعتقد أن الشمس كانت بعيدة جدًا لدرجة أن أشعةها كانت متوازية. يُعتقد أيضًا أن إراتوستينس صنع كتالوجًا للنجوم يضم ما يقرب من 675 نجمة وأنشأ تقويمًا يتضمن سنوات كبيسة.

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

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


تعريفات

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

هذا يعني أن هناك أرقامًا موجودة لا أولي ولا مركب مثل 0 و 1 وأي أعداد غير صحيحة.

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

حاليًا ، تم العثور على أكبر عدد أولي معروف في عام 2013 وهو 17،425،170 رقمًا! الرقم كبير جدًا لدرجة أنه يتم تسجيله على النحو التالي:

يسمي علماء الرياضيات الأعداد الأولية التي تقل بمقدار واحد عن قوة 2 (مثل الموجودة أعلاه) ميرسين برايمز سمي على اسم عالم الرياضيات الفرنسي في القرن السابع عشر ، ومنظر الموسيقى ، ورهبان مينيم مارين ميرسين.

يعد اكتشاف رقم أولي جديد إنجازًا جديرًا بالملاحظة ويمكن أن يكسبك ثروة صغيرة. تتعهد مؤسسة Electronic Frontier Association بمنح 150 ألف دولار لأول شخص أو مجموعة تكتشف عددًا أوليًا لا يقل عن 100،000،000 رقم و 250 ألف دولار لأول شخص أو مجموعة تكتشف عددًا أوليًا لا يقل عن 1،000،000،000 رقم.

كيف نعرف أن الأعداد الأولية بهذا الحجم موجودة؟

في الدرس التالي ، سأريكم كيف نحن نعلم أن هناك عددًا لا نهائيًا من الأعداد الأولية. ابقي على اتصال!

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

(ملاحظة: إذا كان لديك أطفال ، فهذا تمرين تمهيدي رائع. اعرف ما إذا كان يمكنك مساعدتهم في معرفة كيفية حذف الأرقام للعثور على الأعداد الأولية.)


Python Math: طباعة جميع الأعداد الأولية (غربال إراتوستينس) الأصغر من أو تساوي عددًا محددًا

اكتب برنامج Python لطباعة جميع الأعداد الأولية (Sieve of Eratosthenes) أصغر من أو تساوي رقمًا محددًا.

في الرياضيات ، يعتبر غربال إراتوستينس ، أحد غرابيل الأعداد الأولية ، خوارزمية قديمة بسيطة لإيجاد جميع الأعداد الأولية حتى أي حد معين. يقوم بذلك عن طريق وضع علامة تكرارية على مضاعفات كل رئيس (أي ليس أوليًا) ، بدءًا من مضاعفات 2.

عرض مصور:

اعتمادات الرسوم المتحركة: معلومات المؤلف هنا

نموذج للحل:-

كود بايثون:



نظرية الأعداد الأساسية -2

يعد مفهوم الأعداد الأولية مفهومًا مهمًا جدًا في الرياضيات. تتناول هذه المقالة مفهوم الأعداد الأولية والخصائص ذات الصلة.

ما هي الأعداد الأولية والأعداد المركبة؟

الأعداد الأولية هي تلك الأعداد الأكبر من 1 ولها عاملين فقط 1 ونفسها.

الأرقام المركبة هي أيضًا أرقام أكبر من 1 ولكنها تحتوي على قاسم واحد آخر على الأقل بخلاف 1 ونفسها.

على سبيل المثال ، 5 عدد أولي لأن الرقم 5 يقبل القسمة على 1 و 5 فقط. ومع ذلك ، 6 هو رقم مركب لأن 6 يقبل القسمة على 1 و 2 و 3 و 6.

هناك طرق مختلفة للتحقق مما إذا كان الرقم أوليًا.

نهج ساذج

اجتياز جميع الأرقام من $ 1 إلى $ N $ واحسب عدد القواسم. إذا كان عدد القواسم يساوي 2 ، فإن الرقم المحدد يكون أوليًا ، وإلا فهو ليس كذلك.

التعقيد الزمني لهذه الوظيفة على) لأنك تنتقل من $ 1 $ إلى $ N $.

نهج أفضل

إذا كان لديك رقمان موجبان $ N $ و $ D $ ، فإن $ N $ قابل للقسمة على $ D $ و $ D $ أقل من الجذر التربيعي لـ $ N $.

  • يجب أن يكون $ (N / D) $ أكبر من الجذر التربيعي لـ $ N $.
  • $ N $ قابل للقسمة أيضًا على $ (N / D) $. إذا كان المقسوم عليه $ N $ أقل من الجذر التربيعي لـ $ N $ ، فسيكون هناك قاسم قيمته $ N $ أكبر من الجذر التربيعي لـ $ N $. سيكون عليك اجتياز حتى الجذر التربيعي لـ $ N $.

ملحوظة: أنت تولد جميع قواسم $ N $ وإذا كان عدد القواسم أكبر من 2 ، فسيكون الرقم مركبًا.

على سبيل المثال ، إذا كان N = 50 ، فإن $ sqrt N $ = 7 (قيمة أرضية). سوف تتكرر من 1 إلى 7 وتحسب عدد قواسم N.. المقسومات على $ N $ هي 1، 50 2، 25 5،10. لديك 6 قواسم للعدد 50 ، وبالتالي فهي ليست أعدادًا أولية.

التعقيد الزمني لهذه الوظيفة هو $ O ( sqrt N) $ لأنك تنتقل من 1 إلى $ sqrt N $.

منخل إراتوستينس

يمكنك استعمال ال منخل إراتوستينس لإيجاد جميع الأعداد الأولية الأصغر من أو تساوي عددًا معينًا N أو لمعرفة ما إذا كان الرقم عددًا أوليًا.

الفكرة الأساسية وراء Sieve of Eratosthenes هي أنه في كل تكرار يتم التقاط رقم أولي واحد ويتم التخلص من جميع مضاعفاته. بعد اكتمال عملية الحذف ، تكون جميع الأرقام غير المميزة المتبقية أولية.

  1. ضع علامة على جميع الأرقام كأعداد أولية باستثناء 1
  2. مرر فوق كل أعداد أولية أصغر من الجذر التربيعي (N)
  3. لكل عدد أولي ، ضع علامة على مضاعفاته كأرقام مركبة
  4. ستظل الأعداد ، التي ليست مضاعفات أي رقم ، مميزة كرقم أولي وسيتغير البعض الآخر إلى أرقام مركبة.

سيحسب هذا الرمز جميع الأعداد الأولية الأصغر من أو التي تساوي N.

دعونا نحسب الأعداد الأولية حيث $ N = 10 $.

في كل تكرار ، تحقق مما إذا كان الرقم أوليًا أم لا ، وما إذا كان قد تم وضع علامة على كل مضاعفاته كمركب.

الأعداد الأولية هي 2 و 3 و 5 و 7.

تعقيد الوقت
الحلقة الداخلية التي تعمل لكل عنصر هي كما يلي:

  1. إذا كانت i = 2 ، فإن الحلقة الداخلية تعمل N / 2 مرة
  2. إذا كانت i = 3 ، فإن الحلقة الداخلية تعمل N / 3 مرات
  3. إذا كانت i = 5 ، فإن الحلقة الداخلية تعمل N / 5 مرات

مرجع لتحليل التعقيد: غربال Erastothenes

تعديل منخل إراتوستينس للتحليل السريع

عند الخروج من الحلقة for ، فإن $ res vector $ هو التحليل إلى عوامل $ N = 50 $.

في كل خطوة ، يجب أن تبحث عن الرقم الأولي لأقل قيمة ، والذي يقسم $ N $ الحالي. هذه هي الفكرة الرئيسية لهذا التعديل.

دعونا ننشئ مصفوفة ستعطينا هذا الرقم يا (1) زمن.

الآن ، استخدم هذا التعديل لتحليل $ N $ في O (تسجيل (N)) زمن.

العوامل المطلوبة في $ res $.

يمكنك تنفيذ هذا التعديل فقط إذا كان مسموحًا لك بإنشاء مصفوفة أعداد صحيحة بحجم $ N $.

ملحوظة: هذا الأسلوب مفيد عندما تحتاج إلى تحليل أعداد غير كبيرة جدًا. ليس من الضروري بناء غربال معدل لكل مشكلة تتطلب التحليل إلى عوامل. علاوة على ذلك ، لا يمكنك إنشاؤه للأعداد الكبيرة $ N $ مثل $ 10 ^ 9 $ أو $ 10 ^ <12> $. لذلك ، بالنسبة لهذه الأعداد الكبيرة ، فمن المستحسن أن تأخذ في الحسبان O (sqrt (N)) في حين أن.

إذا كان معامل $ N $ هو $ p_1 ^ * ص_2 ^ *. * ص_ك ^$ حيث $ p_1 ، p_2 $. $ p_k $ هما العاملان الأساسيان لكل من $ N $ و $ q_1 و q_2 $. $ q_k $ هي قوى العوامل الأولية ذات الصلة ، ثم $ N $ لديه $ (q_1 + 1) * (q_2 + 1) *. * (q_k + 1) $ قواسم مميزة.

غربال من إراتوستينس في الجزء:

تحتاج أحيانًا إلى العثور على جميع الأعداد الأولية الموجودة في النطاق $ [L. R] $ وليس في $ [1. N] $ ، حيث يمثل $ R $ عددًا كبيرًا.

مسموح لك بإنشاء مصفوفة أعداد صحيحة بحجم $ (R - L + 1) $.

التنفيذ

التقريبي هو التقريب O (الجذر التربيعي (R))

اقتراحات

يوصى بعدم إنشاء غربال للتحقق من وجود عدة أرقام أولية. استخدم الوظيفة التالية بدلاً من ذلك ، والتي تعمل في س ( sqrt N) $ لكل رقم:


منخل إراتوستينس

حل المسائل بإيجاد العوامل الأولية للأعداد.

اخترع إراتوستينس ، الذي عاش في اليونان من حوالي 276 إلى 195 قبل الميلاد ، نظامًا لإيجاد الأعداد الأولية. يتكون من شطب كل رقم ثاني باستثناء 2 على شبكة ثم كل رقم ثالث باستثناء 3 ، وهكذا. الأعداد التي لم يتم شطبها هي أعداد أولية. (قد يكون من المفيد إجراء مناقشة حول كون 1 عددًا خاصًا من حيث أنه ليس عددًا أوليًا أو غير أولي).

باستخدام المواد

أعط كل طالب نسخة من الشبكة. لاحظ أن الرقم 1 مظلل للإشارة إلى أنه مميز. 2 هو عدد أولي وحلق. ناقش كيفية شطب كل مضاعفات العدد 2. (الإجابة: على سبيل المثال ، اشطب أعمدة كاملة في كل مرة.)

خاتم 3 واشطب كل مضاعفات 3 (أي 6 ، 9 ، 12.). قم بحلقة 5 واشطب مضاعفات الرقم 5. استمر حتى يتم حلق كل الأعداد الأولية 200.

مناقشة: لماذا يسمى هذا المنخل؟

فهم خصائص الأعداد:

صِف كيف يمكنك تحديد ما إذا كان العدد 349 عددًا أوليًا باستخدام غربال إراتوستينس. لا تفعل ذلك في الواقع. هل الطريقة مفيدة بشكل عام؟ ضع في اعتبارك على سبيل المثال اختبار ما إذا كان 179781 عددًا أوليًا.


شاهد الفيديو: Math Motes 2: Sieve of Eratosthenes (ديسمبر 2021).