الگوریتم غربال

الگوریتم غربال:روشی است برای یافتن اعداداول بین اعدادطبیعی

تعریف عدداول:اعدادی هستندکه فقط برخودشان ویک بخشپذیرندیااعدادی که فقط دومقسوم علیه دارندکه شامل 1وخودعددمیباشدواعداداول کوچکتراز20 که کاربردزیادی دارندوشایسته است همیشه به یادداشته باشیم شامل2و3و5و7و11و13و17و19میباشد

تعریف عددمرکب:اعدادی که بیشتراز2مقسوم علیه داشته باشندیااول نباشند

نکته:عدد1نه اول است نه مرکب

توضیح روش الگوریتم غربال:دراین روش سوال ازمامیخواهداعداداول بین یکسری ازاعدادطبیعی راپیداکنیم (مثلابین70تا90)برای حل درکل بایدمضربهای اعداداول راخط بزنیم وهرچه باقی بماندعدداول میباشدحال سوال پیش میآیدتاچه مضربهایی ازاعداداول راخط بزنیم درجواب بایدگفت میتوان جذرحدودی عددبزرگ رابگیریم مثلا بین70تا90جذر90رامحاسبه کرده که حدودا,9میشود حال نزدیکترین عدداول به9همان11میباشدپس برای پیداکردن اعداداول از70تا90کافی است مضربهای 2و3و5و7و11راخط بزنیم باقی مانده هااعداداول میباشند.

اگراعداداز1شروع شوندمثلاسوال بگویداعداداول از1تا40راپیداکنیددراینجاچون ازقبل میدانستیم 1اول نیست آن راخط میزنییم وچون میدانیم2و3و5و7و11,اعدادی اول هستندآنهارانگه داشته ومضربهایشان راخط میزنیم وبرای آنکه بدانیم تاچه مضربهایی خط بزنیم جذرحدودی40(بزرگترین عددازمحدوده ای که سوال داده)عدد6میباشدواولین عدداول نزدیک به 6همان7میباشدپس تامضربهای7راخط بزنیم کافیست وباقی مانده هااعداداول هستند.

منبع:
MATRIS