اكنون همه اعدادي را كه به جز 2 ضرب مي شوند رياضي در برنامه نويسي  بررسي كنيد. حالا ما به شماره 3 مي رويم. اين بررسي نشده است ، بنابراين يك عدد اول است. اكنون همه اعدادي را كه مضرب 3 هستند به جز 3 بررسي كنيد. حالا به 4 برويد. مي بينيم كه اين علامت خورده است - اين مضرب 2 است! بنابراين 4 اول نيست. ما اين كار را ادامه مي دهيم.

اگر تعداد زياد باشد (مثلاً 10^16) ، در اين صورت ما به رياضي در برنامه نويسي  غربال قطعه قطعه نياز داريم.

ايده غربال تقسيم بندي شده اين است كه محدوده [0..n-1] را در بخشهاي مختلف تقسيم كرده و اعداد اول را در همه بخشها يك به يك محاسبه كنيد. اين الگوريتم ابتدا از Simple Sieve براي يافتن اعداد كوچكتر يا مساوي؟ (n) استفاده مي كند. در زير مراحل استفاده شده در غربال قطعه بندي شده آمده است.

1. از Simple Sieve براي يافتن تمام اعداد اول تا ريشه مربع 'n' استفاده كنيد و اين اعداد اوليه را در يك آرايه "prime []" ذخيره كنيد. اعداد اوليه را در يك آرايه ‘prime [] ذخيره كنيد.
2. ما به همه اعداد اول در محدوده [0..n-1] نياز داريم. ما اين محدوده را به بخشهاي رياضي در برنامه نويسي  مختلف تقسيم مي كنيم به طوري كه اندازه هر بخش حداكثر است. n
3. براي هر بخش [كم..بالا] موارد زير را انجام دهيد

• ايجاد يك علامت آرايه [بالا-پايين+1]. در اينجا ما فقط به فضاي O (x) نياز داريم كه در آن x تعداد عناصر در محدوده داده شده است.
• در تمام اعداد اول موجود در مرحله 1 تكرار كنيد.ايرانيان سايبر  براي هر اول ، مضرب آن را در محدوده معين [كم..بالا] علامت گذاري كنيد.

در Simple Sieve ، ما به فضاي O (n) نياز داريم كه ممكن است براي n بزرگ  رياضي در برنامه نويسي امكان پذير نباشد. در اينجا ما به فضاي O (؟ n) نياز داريم و محدوده هاي كوچكتر را در يك زمان پردازش مي كنيم

4. حسابي Modulo ، بيان Modulo و Modulo معكوس

وقتي يك عدد بر ديگري تقسيم مي شود ، عمليات modulo بقيه را پيدا مي كند. با نماد٪ مشخص مي شود.

مثال

فرض كنيد دو عدد 10 و 3 داريد. 10٪ 3 برابر رياضي در برنامه نويسي  1 است زيرا وقتي 10 بر 3 تقسيم مي شود ، باقي مانده 1 است.

خواص

1. (a+b)٪ c = (a٪ c+b٪ c)٪ c
2. (a؟ b)٪ c = ((a٪ c)؟ (b٪ c))٪ c
3. (a؟ b)٪ c = ((a٪ c)؟ (b٪ c)+c)٪ c
4. (a/b)٪ c = ((a٪ c)؟ (b٪ c))٪ c

توجه: در آخرين ويژگي بالا ، d مدول ضرب معكوس b و c است.

چه زماني از اين ويژگي ها استفاده مي شود؟

فرض كنيد a = 10^12 ، b = 10^12 و c = 10^9+7. شما بايد (a؟ b)٪ c را پيدا كنيد. وقتي a را با b ضرب مي كنيد ، پاسخ 10^24 است كه با انواع داده رياضي در برنامه نويسي  هاي صحيح استاندارد مطابقت ندارد. بنابراين ، براي جلوگيري از اين امر ، از ويژگي ها استفاده كرديم. (a؟ b)٪ c = ((a٪ c)؟ (b٪ c))٪ c

افزايش سريع Modulo